6 de noviembre de 2013

Multiples of 3 and 5 - Project Euler, problema 1

El problema dice lo siguiente:
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Es fácil ver que solamente es necesario tener una función que calcule los múltiplos de un número m, menores que un número n, dados.

Por ejemplo, para $m=3$ y $n=10$ basta con empezar una lista en 3, y generar múltiplos de este menores que 10 :
$[3, 6, 9] = 3*[1 2 3]$
Y en general:
$[m,  2m,  3m,  ... \lfloor \frac{n-1}{m}\rfloor *m ]$
$=m*[1,  2,  3  ... \lfloor \frac{n-1}{m} \rfloor]$
Eso es bastante fácil de generar en octave y matlab:
(1:floor((n-1)/m))*m
Así que podemos hacer la siguiente función
function y=multip(m,n)
	y=(1:floor((n-1)/m))*m;
end
Ahora, para responder a la pregunta del problema hace falta notar algo mas, y es que para el conjunto de los múltiplos de un número a; y el de un número b se intersectan, es precisamente el conjunto de los múltiplos de a*b. Es decir, que si contamos en los primeros dos conjuntos, tendriamos un algunos números 2 veces. De esta manera solo hace falta "descontar" los números en común en nuestro problema:

n=1000;
sum(multip(3,n))+sum(multip(5,n))-sum(multip(3*5,n))