project euler - problema 5

Hasta ahora a todos los problemas los venia resolviendo por fueza bruta aplicando algunas optimizaciones (para que no sea tan bruto vio?), pero decidi ejercitar un poco mis conocimientos matematicos para intentar resolverlo puramente con matematicas o al menos eliminar muchas cosas innecesarias.

el problema 5 es este:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

agarre un lapiz y un papel (posta!) y me puse a pensar un poco.

Lo primero que probe (fuerza bruta matematica) es el producto de los numeros del 1 al 20 es divisible por todos ellos, el problema es que no es el mas chico.. entonces pense un poco mas. Porque no es el mas chico? bueno, porque ahi hay muchas multiplicaciones innecesarias, si es multiplo de 20 es tambien multiplo de 10, 5, 4 2 etc.

despues de eso llegue a la conclusion de que el numero era el producto de los numeros del 11 al 20, pero resulto no ser asi, pense un rato mas y no se me ocurrio nada asi que decidi darle mi problema acotado a python, lo que hice a grandes rasgos fue.

incrementar de a 380 el contador (producto de 20 y 19), y ya que incremento en multiplos de 20 y 19 no me hace falta controlar que sean multiplos de ellos, por lo tanto hice una lista de numeros del 18 al 11 ya que los numeros mas chicos se comprueban comprobando esos. Puse los numeros al reves ya que si el numero divisor es mas grande tiene menos numeros multiplos, por lo tanto al cortar al encontrar un numero no divisor en los numeros mas grandes me ahorro algunos calculos innecesarios.

cuando entre a las soluciones vi que la solucion del problema tenia que ver con multiplicar numeros, pero no los numeros en si, sino las potencias mas altas de los primos de la factorizacion del 1 al 20. (aca esta la explicacion http://mathforum.org/library/drmath/view/62527.html)

y bue, tan bueno en la matematica no soy :D

codigo en python

NUMS = [float(x) for x in range(11, 19)]
NUMS.reverse()

def first_multiple_from_1_to_20():
num = 380

while True:
for x in NUMS:
if num % x != 0:
break
else:
return num

num += 380

num = first_multiple_from_1_to_20()

print num

-module(ej_005).
-export([first_multiple_from_1_to_20/0]).

is_multiple_from_11_to_18(_Value, 10) -> true;
is_multiple_from_11_to_18(Value, Number) ->
case Value rem Number == 0 of
true -> is_multiple_from_11_to_18(Value, Number - 1);
false -> false
end.

is_multiple_from_11_to_18(Value) -> is_multiple_from_11_to_18(Value, 18).

first_multiple_from_1_to_20(Count) ->
case is_multiple_from_11_to_18(Count) of
true -> Count;
false -> first_multiple_from_1_to_20(Count + 380)
end.

first_multiple_from_1_to_20() -> first_multiple_from_1_to_20(380).

(defun is-multiple-from-11-to-18 (value)
(= (loop for i from 18 downto 11 by 1
while (= (mod value i) 0) finally (return i)) 10))

(defun first-multiple-from-1-to-20 ()
(loop for i from 380 by 380 
while (not (is-multiple-from-11-to-18 i))
finally (return i)))

(print (first-multiple-from-1-to-20))