You are currently browsing the monthly archive for octubre 2016.

Esta es la primera de una serie de publicaciones en las que iré resolviendo los problemas planteados en el Proyecto Euler. El siguiente es el problema a tratar:

Exercise 1 Si listamos los números naturales menores que 10 y múltiplos de {3} o {5}, obtenemos {3}, {5}, {6} y {9}; cuya suma es {23}. Hallar las suma de los múltiplos de {3} o {5} menores que {1000}.

Un primer enfoque sencillo es el siguiente:

  suma = 0
  for n in range(1000):
    if n % 3 == 0 or n % 5 == 0:
      suma += n

O más al estilo Python:

  sum(n for n in range(1000) if n % 3 == 0 or n % 5 == 0)

No obstante, si el proceso no se restringe a {1000}, el método es claramente ineficiente.

¿Cómo podríamos calcular la suma para los múltiplos menores que un millón sin afectar el desempeño?

Empecemos analizando un problema más sencillo. ¿Cómo calcularíamos las suma de los múltiplos de {k} menores que {N}? (Considerar que {k<N}.)

Procedamos de manera intuitiva. Básicamente queremos calcular {1k+2k+3k+4k+5k+\dotsb+nk}, donde {nk} es el último múltiplo de {k} que es menor que {N}. Es decir, queremos calcular {k(1+2+3+4+5+\dotsb+n)}, lo que se resume a evaluar {kn(n+1)/2}. Luego, sólo nos queda resolver cómo obtener {n} que es el máximo factor que cumple {nk<N}, lo que a su vez cumple {n<N/k}. Entonces, para hallar {n} basta con dividir {N} por {k} y fijar el mayor {n} que sea menor que dicho cociente.

Ahora bien, veamos cómo proceder para demostrar que obtendremos realmente la suma. Denotamos con {M_k^N} al conjunto de los múltiplos de {k} menores que {N}. De esta manera, lo que buscamos es evaluar

\displaystyle  \sum_{n\in M_k^N} n.

Así, hemos definido {M_k^N} de manera que {M_k^N:=\{ck:ck<N,\,c\in\mathbf N\}}. (Es sencillo probar que dicho conjunto es el que buscamos. Notar además que se usa el Axioma de sustitución. Dejo al lector el probar que de la definición de múltiplo se llega la definición del conjunto presentado.)

Consideremos las siguientes definición y proposición:

Definition 1 (Múltiplo) Decimos que un número natural {m} es múltiplo de un número natural {n} si se cumple que {m=kn} para algún número natural {k}.

Proposition 2 Sea {X} un conjunto finito, {f\colon X\rightarrow\mathbf R} una función y {g\colon Y\rightarrow X} una biyección. Entonces

\displaystyle  \sum_{x\in X}f(x) = \sum_{y\in Y}g\circ f(y).

Proposition 3 Sea {X} un conjunto finito, {f\colon X\rightarrow\mathbf R} una función y {c} un números real. Entonces

\displaystyle  \sum_{x\in X}cf(x) = c\sum_{x\in X}f(x).

Usando la Proposición 2 y 3, obtenemos que

\displaystyle  \sum_{n\in M_k^N}n=\sum_{n\in I_k^N}kn=k\sum_{n\in I_k^N}n.

donde {I_k^N=\{n\in\mathbf N: kn<N\}}.

Es sencillo ver que en {I_k^N} se encuentran los números de la sucesión {1,2,3,4,5,\dotsc,L} donde {L} es el mayor número de manera que {Lk<N}. Así, la cuestión es cómo calculamos {L}. Bien, tenemos que {L=\max I_k^N}. Como {Lk<N}, se cumple {L\le (N-1)/k}. Por otro lado, tenemos que {(N-1)/k<L-1} ya que {(L+1)k\ge N}. Lo que por definición es la parte entera de {(N-1)/k}, es decir, concluimos que {L=\lfloor(N-1)/k\rfloor}. Así, por definición de serie finita tenemos que

\displaystyle  \sum_{n\in M_k^N}n=\sum_{n=1}^{\left\lfloor\frac{N-1}k\right\rfloor}kn.

Ahora podemos calcular la suma de los múltiplos de {3} menores que {10}, {100} o {1000} respectivamente:

\displaystyle  \begin{aligned}3\sum_{n=1}^{3}n&=3\times\frac{3\times4}2=18\\3\sum_{n=1}^{33}n&=3\times\frac{33\times34}2=1683\\ 3\sum_{n=1}^{333}n&=3\times\frac{333\times334}2=166833\end{aligned}

Todavía nos queda resolver cómo calcular dicha suma para los que son múltiplos de {3} o {5}; no de uno solo de ellos. No basta con sumar las sumas de los múltiplos de {3} y la suma de los múltiplos de {5}, es decir, se cumple {\sum_{n\in M_{3\text{ o }5}^{1000}}n\ne\sum_{n\in M_3^{1000}}n+\sum_{n\in M_{5}^{1000}}n} porque estamos sumando dos veces los múltiplos de {3} que a su vez son múltiplos de {5}. Podemos usar el Principio de inclusión-exclusión. Si {M_{3\text{ o }5}^{1000}} es el conjunto de los múltiplos de {3} o {5} menores que {1000}, tenemos que {\sum_{n\in M_{3\text{ o }5}^{1000}}n=\sum_{n\in M_3^{1000}}n+\sum_{n\in M_{5}^{1000}}n-\sum_{n\in M_{3\text{ y }5}^{1000}}n}. ¿Cómo calculamos {\sum_{n\in M_{3\text{ y }5}^{1000}}n}?

Para que un número {n} sea múltiplo de {3} y {5} tiene que ser de la forma {n=3k} para algún número natural {k}. Luego, como {n} también es múltiplo de {5}, tenemos que {k=5k'} donde {k'} es un número natural. Por lo tanto, obtenemos {n=3\cdot5k'=15k'}, es decir, {n} es múltiplo de {3} y {5} si es múltiplo de {15}. (Incluso podríamos generalizar esto.)

En consecuencia

\displaystyle  \begin{array}{ccccccc} \displaystyle\sum_{n\in M_{3\text{ o }5}^{1000}}n&=&\displaystyle\sum_{n\in M_3^{1000}}n&+&\displaystyle\sum_{n\in M_{5}^{1000}}n&-&\displaystyle\sum_{n\in M_{3\text{ y }5}^{1000}}n\\&=&\displaystyle\sum_{n=1}^{333}3n&+&\displaystyle\sum_{n=1}^{199}5n&-&\displaystyle\sum_{n=1}^{66}15n\\&=&3\times\left(\displaystyle\frac{333\times334}2\right)&+&5\times\left(\displaystyle\frac{199\times200}2\right)&-&15\times\left(\displaystyle\frac{66\times67}2\right)\\&=&233168\end{array}

🙂