IMO – Vestigium

Sucesiones auto descriptivas en Haskell

PorJosé A. Alonso 22 septiembre 201322 septiembre 2013

En las Olimpiadas de Matemáticas del 2001 se propuso el siguiente problema

Buscar todas las sucesiones finitas (x(0), x(1),…,x(n)) tales que para todo j, 0 ≤ j ≤ n, x(j) es igual al número de veces que aparece j en la sucesión.

Las sucesiones que cumplen la anterior condición se llaman auto descriptivas. Un ejemplo de sucesión auto descriptiva es [5,2,1,0,0,1,0,0,0] ya que

el 0 aparece 5 veces,
el 1 aparece 2 veces,
el 2 aparece 1 vez,
el 3 aparece 0 veces,
el 4 aparece 0 veces,
el 5 aparece 1 vez,
el 6 aparece 0 veces,
el 7 aparece 0 veces y
el 8 aparece 0 veces.

En la siguiente relación de ejercicios, elaborada para la asignatura de Informática (de 1º del Grado en Matemáticas) y para la siguiente versión del libro Piensa en Haskell, se resuelve el problema con Haskell.
Read More “Sucesiones auto descriptivas en Haskell”

El problema de las sucesiones llenas en Haskell

PorJosé A. Alonso 16 septiembre 2013

En las Olimpiadas de Matemáticas del 2002 se propuso el siguiente problema

Sea n un entero positivo. Una sucesión de n enteros positivos (no necesariamente distintos) se llama “llena” si verifica la siguiente condición: para cada entero positivo k ≥ 2, si el número k aparece en la sucesión, entonces también lo hace el número k-1 y, además, la primera ocurrencia de k-1 es anterior a la última ocurrencia de k. Para cada n, ¿cuántas sucesiones llenas existen?

En la siguiente relación de ejercicios, elaborada para la asignatura de Informática (de 1º del Grado en Matemáticas), se estudia con Haskell el problema.
Read More “El problema de las sucesiones llenas en Haskell”

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: 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: Número con mayor cantidad de divisores

PorJosé A. Alonso 4 diciembre 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 para la Olimpiada Internacional de Matemáticas de 1983. Su enunciado es

”¿Cuál de los números 1, 2, …, 1983 tiene mayor número de divisores?”

Se van a presentar distintas soluciones y comparar sus eficiciencias. La primera definición es

solucion1 :: Int
solucion1 = head [n | n <- [1..1983], length (divisores1 n) == m]
    where m = maximum [length (divisores1 n) | n <- [1..1983]]

solucion1 :: Int

solucion1 = head [n | n <- [1..1983], length (divisores1 n) == m]

where m = maximum [length (divisores1 n) | n <- [1..1983]]

donde (divisores1 n) es el conjunto de los divisores de n.

divisores1 :: Int -> [Int]
divisores1 n = [x | x <- [1..n], n `rem` x == 0]

1 2	divisores1 :: Int -> [Int] divisores1 n = [x \| x <- [1..n], n `rem` x == 0]

El cálculo con la primera definición es

ghci> solucion1
1680
(9.00 secs, 383804180 bytes)

ghci> solucion1

1680

(9.00 secs, 383804180 bytes)

En la segunda definición se cambia la definición de divisores

divisores2 :: Int -> [Int]
divisores2 n = n : [x | x <- [1..div n 2], n `rem` x == 0]

solucion2 :: Int
solucion2 = head [n | n <- [1..1983], length (divisores2 n) == m]
    where m = maximum [length (divisores2 n) | n <- [1..1983]]

divisores2 :: Int -> [Int]

divisores2 n = n : [x | x <- [1..div n 2], n `rem` x == 0]

solucion2 :: Int

solucion2 = head [n | n <- [1..1983], length (divisores2 n) == m]

where m = maximum [length (divisores2 n) | n <- [1..1983]]

El cálculo con la segunda definición es

ghci> solucion2
1680
(4.69 secs, 192555880 bytes)

ghci> solucion2

1680

(4.69 secs, 192555880 bytes)

En la tercera definición se ordenan los pares

solucion3 :: Int
solucion3 = 
    snd (maximum [(length (divisores2 n),n) | n <- [1..1983]])

solucion3 :: Int

solucion3 =

snd (maximum [(length (divisores2 n),n) | n <- [1..1983]])

El cálculo con la tercera definición es

ghci> solucion3
1680
(2.76 secs, 112406152 bytes)

ghci> solucion3

1680

(2.76 secs, 112406152 bytes)

Se observa que el tiempo se ha reducido de 9.00 segundos a 2.76.