El número 2401 es una potencia de la suma de sus dígitos, ya que dicha suma es 7 y 7^4 = 2401.
Definir la lista
potenciaSumaDigitos :: [Integer]
cuyos elementos son los números que son potencias de las sumas de sus dígitos. Por ejemplo,
λ> take 17 potenciaSumaDigitos [0,1,2,3,4,5,6,7,8,9,81,512,2401,4913,5832,17576,19683]
El enunciado del problema 2 de la OME (Olimpiada Matemática Española) del 1998 es
Sea p un número primo. Determinar todos los enteros k tales que sqrt(k² - k*p) es natural.
Definir las funciones
orbita :: Integer -> [Integer] orbitaDePrimo :: Integer -> [Integer]
tales que
take 4 (orbita 6) == [0,-2,6,8]
take 5 (orbita 36) == [0,-12,36,48,-64]
take 6 (orbita 9) == [0,-3,9,12,-16,25]
take 8 (orbita 27) == [0,-9,27,36,-48,75,-169,196]
take 10 (orbita 111) == [0,-37,111,148,-289,400,-972,1083,-3025,3136]
orbitaDePrimo 5 == [0,-4,5,9]
orbitaDePrimo (primes !! (10^6)) == [0,15485867,-59953011442489,59953026928356]
El enunciado del problema 2 de la OME (Olimpiada Matemática Española) del 1998 es
Hallar todos los números naturales de 4 cifras, escritos en base 10, que sean iguales al cubo de la suma de sus cifras.
Definir la función
especiales :: Integer -> Integer -> [Integer]
tal que (especiales a b) es la lista de los números de a cifras que son iguales la suma de sus cifras elevada a b. Por ejemplo,
especiales 5 3 == [17576,19683] especiales 6 4 == [234256,390625,614656]
Usando la función anterior, calcular las soluciones del problema de la Olimpiada.
El enunciado del problema 5 de la OME (Olimpiada Matemática Española) del 2002 es
La función g se define sobre los números naturales y satisface las condiciones:
- g(1) = 1
- g(2n) = g(n)
- g(2n + 1) = g(2n) + 1
Sea n un número natural tal que 1 ≤ n ≤ 2002. Calcula el valor máximo M de g(n). Calcula también cuántos valores de n satisfacen g(n) = M.
Los valores de la función g para n de 1 a 30 son
1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4
Definir la función
maximoG :: Integer -> Integer
tal que (maximoG m) es el máximo de los valores de g(n) para n en {1, 2,..., m}. Por ejemplo,
maximoG 30 == 4 maximoG (10^(10^5)) == 332192
Usando la función maximoG, calcular los valores pedidos en el problema.
El enunciado del problema 5 de la OME (Olimpiada Matemática Española) del 2006 es
Probar que el producto de cuatro naturales consecutivos no puede ser ni cuadrado ni cubo perfecto.
Definir la lista
productos :: [Integer]
cuyos elementos son los productos de cuatro enteros positivos consecutivos. Por ejemplo,
λ> take 12 productos [24,120,360,840,1680,3024,5040,7920,11880,17160,24024,32760]
Comprobar con QuickCheck que los elementos de la lista anterior no son ni cuadrados ni cubos perfectos.
El enunciado del problema 4 de la OME (Olimpiada Matemática Española) del 2014 es
Sea {x(n)} la sucesión de enteros positivos definida por x(1) = 2 y x(n+1) = 2*x(n)^3+x(n) para todo n >= 1. Determinar la mayor potencia de 5 que divide al número x(2014)^2+1.
Definir la función
mayorExponente :: Integer -> Integer
tal que (mayorExponente n) es el mayor m tal que 5^m divide al número x(n)^2+1.
El enunciado del problema 5 de la OME (Olimpiada Matemática Española) del 2016 es
De entre todas las permutaciones (a(1), a(2),..., a(n)) del conjunto {1, 2,..., n},(n ≥ 1 entero), se consideran las que cumplen que 2(a(1) + a(2) +···+ a(m)) es divisible por m, para cada m = 1, 2,..., n. Calcular el número total de estas permutaciones.
Llamaremos permutaciones divisibles a las que cumplen la propiedad anterior. Por ejemplo, [2,3,4,1] es una permutación divisible de {1,2,3,4} ya que es una permutación del conjunto y se cumplen las condiciones:
Definir las siguientes funciones:
permutacionesDivisibles :: Integer -> [[Integer]] nPermutacionesDivisibles :: Integer -> Integer
tales que
λ> permutacionesDivisibles 2
[[1,2],[2,1]]
λ> permutacionesDivisibles 3
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
λ> permutacionesDivisibles 4
[[1,2,3,4],[1,3,2,4],[2,1,3,4],[2,3,1,4],[2,3,4,1],[2,4,3,1],
[3,1,2,4],[3,2,1,4],[3,2,4,1],[3,4,2,1],[4,2,3,1],[4,3,2,1]]
λ> length (permutacionesDivisibles 20)
786432
~~~
+ (nPermutacionesDivisibles n) es el número de permutaciones divisibles de {1,2,...,n}. Por ejemplo,
nPermutacionesDivisibles 4 == 12 nPermutacionesDivisibles (10^8) `mod` (10^9) == 340332032
------------------------------------------------------------------------ <!-- TEASER_END --> ## Soluciones ~~~haskell import Data.List (genericLength, permutations, sort) -- 1ª definición de permutacionesDivisibles -- ======================================== permutacionesDivisibles :: Integer -> [[Integer]] permutacionesDivisibles n = sort (filter aux (permutations [1..n])) where aux xs = and [(2*x) `mod` n == 0 | (x,n) <- zip (sumasParciales xs) [1..]] -- (sumasParciales xs) es la lista de las suas parciales de xs. Por ejemplo, -- sumasParciales [1..9] == [1,3,6,10,15,21,28,36,45] sumasParciales :: [Integer] -> [Integer] sumasParciales = scanl1 (+) -- 2ª definición de permutacionesDivisibles -- ======================================== permutacionesDivisibles2 :: Integer -> [[Integer]] permutacionesDivisibles2 = sort . aux where aux n | n < 4 = permutations [1..n] | otherwise = [xs ++ [n] | xs <- xss] ++ [map (+1) xs ++ [1] | xs <- xss] where xss = aux (n-1) -- Comprobación de equivalencia -- ============================ -- La comprobación para los n primeros valores es -- λ> and [permutacionesDivisibles2 n == permutacionesDivisibles n | n <- [1..9]] -- True -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (permutacionesDivisibles 10) -- 768 -- (8.42 secs, 10,420,281,776 bytes) -- λ> length (permutacionesDivisibles2 10) -- 768 -- (0.02 secs, 2,250,152 bytes) -- -- λ> length (permutacionesDivisibles2 20) -- 786432 -- (14.33 secs, 4,458,839,736 bytes) -- 1ª definición de nPermutacionesDivisibles -- ========================================= -- nPermutacionesDivisibles 5 == 24 nPermutacionesDivisibles :: Integer -> Integer nPermutacionesDivisibles = genericLength . permutacionesDivisibles -- 2ª definición de nPermutacionesDivisibles -- ========================================= nPermutacionesDivisibles2 :: Integer -> Integer nPermutacionesDivisibles2 = genericLength . permutacionesDivisibles2 -- 3ª definición de nPermutacionesDivisibles -- ========================================= -- Observando los siguientes cálculos: -- λ> [nPermutacionesDivisibles2 n | n <- [1..12]] -- [1,2,6,12,24,48,96,192,384,768,1536,3072] -- λ> 1 : 2 : [3*2^(n-2) | n <- [3..12]] -- [1,2,6,12,24,48,96,192,384,768,1536,3072] nPermutacionesDivisibles3 :: Integer -> Integer nPermutacionesDivisibles3 n | n < 3 = n | otherwise = 3*2^(n-2) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> nPermutacionesDivisibles 10 -- 768 -- (7.95 secs, 10,704,422,592 bytes) -- λ> nPermutacionesDivisibles2 10 -- 768 -- (0.01 secs, 2,269,872 bytes) -- λ> nPermutacionesDivisibles3 10 -- 768 -- (0.01 secs, 102,560 bytes) -- -- λ> nPermutacionesDivisibles2 20 -- 786432 -- (13.00 secs, 4,477,717,968 bytes) -- λ> nPermutacionesDivisibles3 20 -- 786432 -- (0.01 secs, 106,848 bytes)
El enunciado del segundo problema de este mes de la RSME es el siguiente:
Un número de al menos tres cifras se denomina fibonacciano si sus cifras, a partir de la tercera, son iguales a la suma de las dos cifras anteriores. Por ejemplo, 5279 es un número fibonacciano, pues su tercera cifra, 7, es suma de las dos anteriores (5+2) y su cuarta cifra, 9, también (2+7).
Te daremos el problema por válido si respondes bien a estas dos cuestiones: a) ¿cuántas cifras como máximo puede tener un número fibonacciano? b) ¿cuántos números fibonaccianos hay?
En la definición de fibonacciano la suma de las cifras tiene que menor que 10, pero podemos generalizarlo sustituyendo 10 por número n. Dichos números de llaman fibonaccianos generalizados acotados por n. Por ejemplo, 571219315081 es un fibonacciano generalizado acotado por 100 ya que la sucesión de sus dígitos es 5, 7, 12 (= 5+7), 19 (= 7+12), 31 (= 12+19) 50 (=19+31) y 81 (=31+50).
Definir las funciones
esFibonacciano :: Integer -> Bool fibonaccianos :: [Integer] fibonaccianosG :: Integer -> [Integer]
tales que
esFibonacciano 5279 == True
esFibonacciano 527916 == False
λ> take 60 fibonaccianos
[101,112,123,134,145,156,167,178,189,202,213,224,235,246,257,268,
279,303,314,325,336,347,358,369,404,415,426,437,448,459,505,516,
527,538,549,606,617,628,639,707,718,729,808,819,909,1011,1123,
1235,1347,1459,2022,2134,2246,2358,3033,3145,3257,3369,4044,4156]
λ> take 60 (fibonaccianosG 100) [101,112,123,134,145,156,167,178,189,202,213,224,235,246,257,268, 279,303,314,325,336,347,358,369,404,415,426,437,448,459,505,516, 527,538,549,606,617,628,639,707,718,729,808,819,909,1011,1123, 1235,1347,1459,1910,2022,2134,2246,2358,2810,2911,3033,3145,3257] λ> take 12 (drop 60 (fibonaccianosG 10)) [4268,5055,5167,5279,6066,6178,7077,7189,8088,9099,10112,11235] λ> take 12 (drop 60 (fibonaccianosG 100)) [3369,3710,3811,3912,4044,4156,4268,4610,4711,4812,4913,5055] λ> length (fibonaccianosG (10^40)) 16888 λ> length (show (last (fibonaccianosG (10^40)))) 3943
Usando las funciones anteriores, calcular cuántas cifras como máximo puede tener un número fibonacciano y cuántos números fibonaccianos hay.
El enunciado del primer problema de este mes de la RSME es el siguiente:
Un entero positivo de dos o más cifras se denomina cuadriseguido si cada par de dígitos consecutivos que tenga es un cuadrado perfecto. Por ejemplo, + 364 es cuadriseguido, pues 36 = 6^2 y 64 = 8^2 + 3642 no lo es porque 42 no es un cuadrado perfecto. Obtén todos los números cuadriseguidos posibles.
El concepto de cuadriseguido se puede generalizar como sigue: Un entero positivo n de dos o más cifras se denomina encadenado respecto de una lista de números de dos dígitos xs si cada par de dígitos consecutivos que tenga es un elemento distinto de xs. Por ejemplo,
Definir la función
encadenados :: [Integer] -> [Integer]
tal que (encadenados xs) es la lista de los números encadenados respecto de xs. Por ejemplo,
λ> encadenados [12,23,31] [12,23,31,123,231,312,1231,2312,3123] λ> encadenados [12,22,31] [12,22,31,122,312,3122] λ> take 14 (encadenados [n^2 | n <- [4..9]]) [16,25,36,49,64,81,164,364,649,816,1649,3649,8164,81649] λ> length (encadenados [10..42]) 911208
Calcular todos los números cuadriseguidos posibles usando la función encadenados.
En la librería Data.Tree se definen los árboles y los bosques como sigue
data Tree a = Node a (Forest a) type Forest a = [Tree a]
Se pueden definir árboles. Por ejemplo,
ej = Node 3 [Node 5 [Node 9 []], Node 7 []]
Y se pueden dibujar con la función drawTree. Por ejemplo,
λ> putStrLn (drawTree (fmap show ej)) 3 | +- 5 | | | `- 9 | `- 7
Una cadena con un conjunto de pares ps es una lista xs de elementos distintos de ps tales que la segunda componente de cada elemento de xs es igual a la primera componente de su siguiente elemento. Por ejemplo, si ps = [(1,6),(2,5),(3,6),(4,9),(6,4),(8,1)] entonces [(6,4)], [(8,1),(1,6)] y [(8,1),(1,6),(6,4),(4,9)] son cadenas con ps.
Definir la función
arbolCadenas :: Eq a => [(a,a)] -> Tree [(a,a)]
tal que (arbolCadenas ps) es el árbol de las cadenas formadas con los elementos de ps. Por ejemplo,
λ> putStrLn (drawTree (fmap show (arbolCadenas [(1,2),(2,3),(3,1)]))) [] | +- [(1,2)] | | | `- [(3,1),(1,2)] | | | `- [(2,3),(3,1),(1,2)] | +- [(2,3)] | | | `- [(1,2),(2,3)] | | | `- [(3,1),(1,2),(2,3)] | `- [(3,1)] | `- [(2,3),(3,1)] | `- [(1,2),(2,3),(3,1)] λ> putStrLn (drawTree (fmap show (arbolCadenas [(1,6),(2,5),(3,6),(4,9),(6,4),(8,1)]))) [] | +- [(1,6)] | | | `- [(8,1),(1,6)] | +- [(2,5)] | +- [(3,6)] | +- [(4,9)] | | | `- [(6,4),(4,9)] | | | +- [(1,6),(6,4),(4,9)] | | | | | `- [(8,1),(1,6),(6,4),(4,9)] | | | `- [(3,6),(6,4),(4,9)] | +- [(6,4)] | | | +- [(1,6),(6,4)] | | | | | `- [(8,1),(1,6),(6,4)] | | | `- [(3,6),(6,4)] | `- [(8,1)]