I1M2012: Ceros finales del factorial
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la solución con Haskell de un problema propuesto para la Olimpiada Internacional de Matemáticas de 1987 cuyo enunciado es
”Calcular el menor número natural n tal que n! termina exactamente en 1987 ceros.”
Resolverlo con Haskell.
Para resolverlo, empezamos definiendo la función cerosDelFactorial tal que (cerosDelFactorial n) es el número de ceros en que termina el factorial de n. Por ejemplo,
|
1 2 |
cerosDelFactorial1 24 == 4 cerosDelFactorial1 25 == 6 |
Presentamos dos definiciones la primera es
|
1 2 |
cerosDelFactorial1 :: Integer -> Integer cerosDelFactorial1 n = ceros (factorial n) |
donde (ceros n) es el número de ceros en los que termina el número n. Por ejemplo,
|
1 |
ceros 320000 == 4 |
|
1 2 |
ceros n | rem n 10 /= 0 = 0 | otherwise = 1 + ceros (div n 10) |
y (factorial n) es el factorial n. Por ejemplo,
|
1 |
factorial 3 == 6 |
|
1 |
factorial n = product [1..n] |
La segunda es
|
1 2 3 4 |
cerosDelFactorial2 :: Integer -> Integer cerosDelFactorial2 n | n < 5 = 0 | otherwise = m + cerosDelFactorial2 m where m = n `div` 5 |
Se puede comprobar la equivalencia de las dos definiciones
|
1 2 |
ghci> and [cerosDelFactorial1 n == cerosDelFactorial2 n | n <- [1..100]] True |
y que la segunda es más eficiente
|
1 2 3 4 5 6 |
ghci> cerosDelFactorial1 (10^4) 2499 (0.64 secs, 131287116 bytes) ghci> cerosDelFactorial2 (10^4) 2499 (0.01 secs, 725088 bytes) |
En lo que sigue, usaremos la segunda definición
|
1 2 |
cerosDelFactorial :: Integer -> Integer cerosDelFactorial = cerosDelFactorial1 |
A continuación definimos la función menorFactorial tal que (menorFactorial m) es el menor número cuyo factorial termina en m ceros exactamente. Por ejemplo,
|
1 2 3 |
menorFactorial 1 == 5 menorFactorial 4 == 20 menorFactorial 6 == 25 |
|
1 2 |
menorFactorial :: Integer -> Integer menorFactorial k = head [n | n <- [1..], cerosDelFactorial n == k] |
Finalmente definimos la solución del problema; es decir, el menor número natural n tal que n! termina exactamente en 1987 ceros.
|
1 2 |
solucion :: Integer solucion = menorFactorial 1987 |
El cálculo de la solución es
|
1 2 |
ghci> solucion 7960 |