Haskell – Página 90

I1M2012: Ceros finales del factorial

PorJosé A. Alonso 18 diciembre 20128 marzo 2013

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,

cerosDelFactorial1 24  ==  4
cerosDelFactorial1 25  ==  6

1 2	cerosDelFactorial1 24 == 4 cerosDelFactorial1 25 == 6

Presentamos dos definiciones la primera es

cerosDelFactorial1 :: Integer -> Integer
cerosDelFactorial1 n = ceros (factorial n)

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,

ceros 320000  ==  4

1	ceros 320000 == 4

ceros n | rem n 10 /= 0 = 0
        | otherwise     = 1 + ceros (div n 10)

1 2	ceros n \| rem n 10 /= 0 = 0 \| otherwise = 1 + ceros (div n 10)

y (factorial n) es el factorial n. Por ejemplo,

factorial 3  ==  6

1	factorial 3 == 6

factorial n = product [1..n]

1	factorial n = product [1..n]

La segunda es

cerosDelFactorial2 :: Integer -> Integer
cerosDelFactorial2 n | n < 5     = 0
                     | otherwise = m + cerosDelFactorial2 m
                     where m = n `div` 5

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

ghci> and [cerosDelFactorial1 n == cerosDelFactorial2 n | n <- [1..100]]
True

1 2	ghci> and [cerosDelFactorial1 n == cerosDelFactorial2 n \| n <- [1..100]] True

y que la segunda es más eficiente

ghci> cerosDelFactorial1 (10^4)
2499
(0.64 secs, 131287116 bytes)
ghci> cerosDelFactorial2 (10^4)
2499
(0.01 secs, 725088 bytes)

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

cerosDelFactorial :: Integer -> Integer
cerosDelFactorial = cerosDelFactorial1

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,

menorFactorial 1  ==  5
menorFactorial 4  ==  20
menorFactorial 6  ==  25

menorFactorial 1 == 5

menorFactorial 4 == 20

menorFactorial 6 == 25

menorFactorial :: Integer -> Integer
menorFactorial k = head [n | n <- [1..], cerosDelFactorial n == k]

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.

solucion :: Integer
solucion = menorFactorial 1987

1 2	solucion :: Integer solucion = menorFactorial 1987

El cálculo de la solución es

ghci> solucion
7960

1 2	ghci> solucion 7960

I1M2012: El problema de las números bonitos y números feos en Haskell

PorJosé A. Alonso 18 diciembre 201216 marzo 2013

En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la solución con Haskell el desafío matemáticos Números bonitos, números feos publicado en EL PAÍS con motivo del sorteo de la Lotería de Navidad. Su enunciado es

Desde el año 2011 en la Lotería Navidad se sortean los premios entre los cien mil números que van del 00000 al 99999 (en los décimos los números siempre se escriben con cinco cifras). Aunque todos los números tienen exactamente las mismas posibilidades de resultar premiados, con frecuencia se habla de números bonitos y números feos. Como es una valoración estética, que un número sea bonito o feo depende de los gustos de cada uno.

En este caso un número de lotería nos parecerá bonito si cumple
exactamente una, y solamente una, de estas tres condiciones:

a) es divisible entre 5,

b) da resto 2 al dividirlo entre 7,

c) la suma de sus cifras es divisible entre 9.

Por ejemplo, el 00037 es bonito porque cumple la condición b pero no las otras dos; sin embargo, el 00324 es feo, ya que cumple las condiciones b y c. De igual forma, podríamos decir que el 00041 y el 00450 son horribles. El primero, porque no cumple ninguna de las tres condiciones; y el segundo, porque es un exagerado y cumple las tres.

El desafío que se propone es decidir cuántos de los números que participan en el sorteo de Lotería de Navidad (recordad, del 00000 al 99999) son bonitos según el criterio expresado anteriormente.

A continuación, se presentan 5 soluciones en Haskell y se comparan sus eficiencias.
Read More “I1M2012: El problema de las números bonitos y números feos en Haskell”

I1M2012: Suma de números monótonos

PorJosé A. Alonso 11 diciembre 20128 marzo 2013

Calcular la suma de todos los enteros positivos cuyos dígitos forman una sucesión estrictamente creciente o estrictamente decreciente.

Lo resolveremos generando las listas de todos los enteros positivos cuyos dígitos forman una sucesión estrictamente monótona. Para ello nos basaremos en las listas de dígitos que forman una sucesión estrictamente monótona.

Comenzamos con los decrecientes:

(listasDecrecientesDesde n) es la lista de las sucesiones estrictamente decrecientes cuyo primer elemento es n. Por ejemplo,
ghci> listasDecrecientesDesde 3
[[3],[3,2],[3,2,1],[3,2,1,0],[3,2,0],[3,1],[3,1,0],[3,0]]

listasDecrecientesDesde :: Integer -> [[Integer]]
listasDecrecientesDesde 0 = [[0]]
listasDecrecientesDesde n =
    [n] : [n:ys | m <- [n-1,n-2..0], ys <- listasDecrecientesDesde m]

listasDecrecientesDesde :: Integer -> [[Integer]]

listasDecrecientesDesde 0 = [[0]]

listasDecrecientesDesde n =

[n] : [n:ys | m <- [n-1,n-2..0], ys <- listasDecrecientesDesde m]

listasDecrecientes es la lista de las sucesiones estrictamente decrecientes cuyo primer elemento es un dígito. Por ejemplo,
ghci> take 10 listasDecrecientes
[[0],[1],[1,0],[2],[2,1],[2,1,0],[2,0],[3],[3,2],[3,2,1]]

Haskell

listasDecrecientes :: [[Integer]] listasDecrecientes = concat [listasDecrecientesDesde n | n <- [0..9]]

1
2
3

listasDecrecientes :: [[Integer]]
listasDecrecientes =
concat [listasDecrecientesDesde n | n <- [0..9]]
(listaNumero xs) es el número correspondiente a la lista de dígitos xs. Por ejemplo,
listaNumero [3,2,5] == 325

Haskell

listaNumero :: [Integer] -> Integer listaNumero xs = sum [y*10^n | (y,n) <- zip (reverse xs) [0..]]

1
2

listaNumero :: [Integer] -> Integer
listaNumero xs = sum [y*10^n | (y,n) <- zip (reverse xs) [0..]]
numerosDecrecientes es la lista de los enteros positivos cuyos dígitos forman una sucesión estrictamente decreciente. Por ejemplo,
ghci> take 17 numerosDecrecientes
[0,1,10,2,21,210,20,3,32,321,3210,320,31,310,30,4,43]

Haskell

numerosDecrecientes :: [Integer] numerosDecrecientes = [listaNumero xs | xs <- listasDecrecientes]

1
2

numerosDecrecientes :: [Integer]
numerosDecrecientes = [listaNumero xs | xs <- listasDecrecientes]

Análogamente se construyen los crecientes:

(listasCrecientesDesde n) es la lista de las sucesiones estrictamente crecientes cuyo primer elemento es n. Por ejemplo,
ghci> listasCrecientesDesde 6
[[6],[6,7],[6,7,8],[6,7,8,9],[6,7,9],[6,8],[6,8,9],[6,9]]

listasCrecientesDesde :: Integer -> [[Integer]]
listasCrecientesDesde 9 = [[9]]
listasCrecientesDesde n =
    [n] : [n:ys | m <- [n+1..9], ys <- listasCrecientesDesde m]

listasCrecientesDesde :: Integer -> [[Integer]]

listasCrecientesDesde 9 = [[9]]

listasCrecientesDesde n =

[n] : [n:ys | m <- [n+1..9], ys <- listasCrecientesDesde m]

listascrecientes es la lista de las sucesiones estrictamente crecientes cuyo primer elemento es un dígito. Por ejemplo,
ghci> take 5 listasCrecientes
[[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5]]

Haskell

listasCrecientes :: [[Integer]] listasCrecientes = concat [listasCrecientesDesde n | n <- [1..9]]

1
2
3

listasCrecientes :: [[Integer]]
listasCrecientes =
concat [listasCrecientesDesde n | n <- [1..9]]
numerosCrecientes es la lista de los enteros positivos cuyos dígitos forman una sucesión estrictamente creciente. Por ejemplo,
ghci> take 5 numerosCrecientes
[1,12,123,1234,12345]

Haskell

numerosCrecientes :: [Integer] numerosCrecientes = [listaNumero xs | xs <- listasCrecientes]

1
2

numerosCrecientes :: [Integer]
numerosCrecientes = [listaNumero xs | xs <- listasCrecientes]

Con las definiciones anteriores la solución es inmediata:

Haskell

solucion :: Integer solucion = sum (numerosCrecientes ++ numerosDecrecientes) - sum [1..9]

1
2
3

solucion :: Integer
solucion =
sum (numerosCrecientes ++ numerosDecrecientes) - sum [1..9]

El cálculo de la solución es

ghci> solucion 25617208995

1
2

ghci> solucion
25617208995

I1M2012: Sumas de factoriales que dan cuadrados perfectos

PorJosé A. Alonso 27 noviembre 20128 marzo 2013

En la primera parte de 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 en la revista Mathematics Magazine. Su enunciado es

Encontrar todos los enteros positivos m y n para los que se
cumpla que: $1!+2!+3!+ \dots +n!=m^2$ .

Su traducción directa es

sol :: [(Integer,Integer)]
sol = [(n,m) | n <- [1..], m <- [sumaFactoriales n], esCuadrado m]

1 2	sol :: [(Integer,Integer)] sol = [(n,m) \| n <- [1..], m <- [sumaFactoriales n], esCuadrado m]

o, usando let,

sol' :: [(Integer,Integer)]
sol' = [(n,m) | n <- [1..], let m = sumaFactoriales n, esCuadrado m]

1 2	sol' :: [(Integer,Integer)] sol' = [(n,m) \| n <- [1..], let m = sumaFactoriales n, esCuadrado m]

donde

(sumaFactoriales n) es la suma de los factoriales de 1 a n

Haskell

sumaFactoriales :: Integer -> Integer sumaFactoriales n = sum [factorial x | x <- [1..n]]

1
2

sumaFactoriales :: Integer -> Integer
sumaFactoriales n = sum [factorial x | x <- [1..n]]
(factorial n) es el factorial de n.

Haskell

factorial :: Integer -> Integer factorial n = product [1..n]

1
2

factorial :: Integer -> Integer
factorial n = product [1..n]
(esCuadrado x) se verifica si x es un cuadrado perfecto.

Haskell

esCuadrado :: Integer -> Bool esCuadrado x = x == y*y where y = floor (sqrt (fromIntegral x))

1
2
3

esCuadrado :: Integer -> Bool
esCuadrado x = x == y*y
where y = floor (sqrt (fromIntegral x))

Con esta definición se encuentran las siguientes soluciones

ghci> sol
[(1,1),(3,9)  
C-c C-c
Interrupted.

ghci> sol

[(1,1),(3,9)

C-c C-c

Interrupted.

Se observa que después de calcular las dos primeras sigue buscando por lo que hay que terminar el cálculo (con C-c C-c) sin encontrar más soluciones.

Que las dos primeras son soluciones se comprueba fácilmente:

$1! = 1 = 1^2$
$1!+2!+3! = 9 = 3^2$ .

Vamos a investigar porqué no hay más soluciones. Para ello, empezamos calculando las sumas de los factoriales

ghci> [sumaFactoriales n | n <- [1..10]]
[1,3,9,33,153,873,5913,46233,409113,4037913]

1 2	ghci> [sumaFactoriales n \| n <- [1..10]] [1,3,9,33,153,873,5913,46233,409113,4037913]

Se observa que, a partir de la cuarta, todas terminan en 3. Por otra parte, calculando los cuadrados de los dígitos

ghci> [x^2 | x <- [0..9]]
[0,1,4,9,16,25,36,49,64,81]

1 2	ghci> [x^2 \| x <- [0..9]] [0,1,4,9,16,25,36,49,64,81]

se observa que ninguno termina en 3; es decir, ningún cuadrado perfecto temina en 3.

Para terminar, nos falta demostrar la conjetura anterior (si n>3, entonces $1!+2!+3!+ \dots +n!$ termina en 3). Para ello calculamos los primeros factoriales

ghci> [factorial n | n <- [1..10]]
[1,2,6,24,120,720,5040,40320,362880,3628800]

1 2	ghci> [factorial n \| n <- [1..10]] [1,2,6,24,120,720,5040,40320,362880,3628800]

Se observa que para n=4 termina en 3 (es 1+2+6+24=33) y que, para n>4, el último dígito de n! es 0 (que es fácil de demostrar ya que si n>4, entre los factores de n están el 2 y el 5).

I1M2012: Último dígito del producto de números de Fermat

PorJosé A. Alonso 20 noviembre 20128 marzo 2013

En la segunda parte de 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 (IMO) de 1971. Su enunciado es

Sea $x_n = 2^{2^n} + 1$ y sea $m$ el producto de $x_2, x_3, \dots, x_{1971}$ . Calcular el último dígito de $m$ .

La primera definición es la traducción directa del enunciado

sol1 :: Integer
sol1 = ultimo (product [x n | n <- [2..1971]])

1 2	sol1 :: Integer sol1 = ultimo (product [x n \| n <- [2..1971]])

donde (x n) es el n-ésimo término de la sucesión

x :: Int -> Integer 
x n = 2^(2^n) + 1

1 2	x :: Int -> Integer x n = 2^(2^n) + 1

y (ultimo x) es el último dígito de x

ultimo :: Integer -> Integer
ultimo x = rem x 10

1 2	ultimo :: Integer -> Integer ultimo x = rem x 10

Aunque la primera solución es simple, tiene un inconveniente: Haskell no puede calcular números tan grandes. Una estrategia para resolverlo es considerar casos menores y buscar alguna regularidad. Para ello, generalizamos la primera solución sustituyendo 1971 por una variable.

sol2 :: Int -> Integer
sol2 a = ultimo (product [x n | n <- [2..a]])

1 2	sol2 :: Int -> Integer sol2 a = ultimo (product [x n \| n <- [2..a]])

Con la 2ª definición calculamos el último dígito de los primeros productos

ghci> [sol2 a | a <- [2..20]] 
[7,9,3,1,7,9,3,1,7,9,3,1,7,9,3,1,7,9,3]

1 2	ghci> [sol2 a \| a <- [2..20]] [7,9,3,1,7,9,3,1,7,9,3,1,7,9,3,1,7,9,3]

Se observa que el resultado está formado por la repetición de los números 7, 9, 3 y 1. A partir de la observación conjeturamos una nueva definición

sol3 :: Int -> Integer
sol3 a | b == 2 = 7
       | b == 3 = 9
       | b == 0 = 3
       | b == 1 = 1
       where b = rem a 4

sol3 :: Int -> Integer

sol3 a | b == 2 = 7

| b == 3 = 9

| b == 0 = 3

| b == 1 = 1

where b = rem a 4

Podemos comprobar, para pequeños valores, que las 2 definiciones son equivalentes

ghci> [sol2 a | a <- [2..20]] == [sol3 a | a <- [2..20]] 
True

1 2	ghci> [sol2 a \| a <- [2..20]] == [sol3 a \| a <- [2..20]] True

Además, con la 3ª definición se puede calcular la solución del problema original

ghci> sol3 1971
9

1 2	ghci> sol3 1971 9

es decir, el último dígito del producto $x_2x_3 \dots x_{1971}$ es 9.

Para justificar la solución, hay que demostrar que la definición sol3 es correcta; es decir, que los últimos dígitos de los productos forman la sucesión 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3, … Para ello, observamos el último dígito de los $x_n$

ghci> [ultimo (x n) | n <- [2..20]]
[7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7]

1 2	ghci> [ultimo (x n) \| n <- [2..20]] [7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7]

Se observa que todos son 7. Esto justifica la sucesión de los productos, ya que cada término es el último dígito del producto del anterior por 7. Además, permite una nueva definición de la solución por recursión

sol4 :: Int -> Integer
sol4 a | a == 2    = 7
       | otherwise = ultimo (7 * sol4 (a-1))

sol4 :: Int -> Integer

sol4 a | a == 2 = 7

| otherwise = ultimo (7 * sol4 (a-1))

Podemos comprobar, para pequeños valores, que es equivalente a la anterior

ghci> [sol3 a | a <- [2..20]] == [sol4 a | a <- [2..20]] 
True

1 2	ghci> [sol3 a \| a <- [2..20]] == [sol4 a \| a <- [2..20]] True

Para terminar, sólo queda demostrar que si $n>1$ , entonces el último dígito de $2^{2^n} + 1$ es 7 o, equivalentemente, que el último dígito de $2^{2^n}$ es 6. Lo que se tiene ya que $2^{2^n} = 2^{2\cdot2^{n-1}} = (2^2)^{2^{n-1}} = 4^{2^{n-1}}$ . Además, como $n>1$ se tiene que $2^{n-1}$ es un número par mayor que 0 y, por tanto, el último dígito de $4^{2^{n-1}}$ es 6.