Menu Close

Autor: José A. Alonso

Permutaciones divisibles (OME2016 P5)

José A. Alonso---1 Comentario

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:

  • 2*2 = 4 es divisible por 1,
  • 2*(2+3) = 10 es divisible por 2
  • 2*(2+3+4) = 18 es divisible por 3.
  • 2*(2+3+4+1) = 20 es divisible por 4.

Definir las siguientes funciones:

   permutacionesDivisibles  :: Integer -> [[Integer]]
   nPermutacionesDivisibles :: Integer -> Integer

tales que

  • (permutacionesDivisibles n) es la lista de las permutaciones divisibles de {1,2,…,n}. Por ejemplo,
     λ> 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

Soluciones

  • Las soluciones se pueden escribir en los comentarios hasta el 29 de abril.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Seguir leyendo →

Números fibonaccianos

José A. Alonso---1 Comentario

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 n) se verifica si n es un número fibonacciano. Por ejemplo,
     esFibonacciano 5279    ==  True
     esFibonacciano 527916  ==  False
  • fibonaccianos es la lista de los números fibonaccianos. Por ejemplo,
     λ> 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]
  • (fibonaccianosG n) es la lista de los números fibonaccianos generalizados acotados por n. Por ejemplo,
     λ> 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.

Soluciones

  • Las soluciones se pueden escribir en los comentarios hasta el 28 de abril.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Seguir leyendo →

Cuadriseguidos y números encadenados

José A. Alonso---3 Comentarios

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,

  • 364 es encadenado respecto de xs = [36,64,15], porque 36 y 64 pertenecen a xs
  • 3642 no es encadenado respecto de xs = [36,64,15], porque 42 no pertenece a xs

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.

Soluciones

  • Las soluciones se pueden escribir en los comentarios hasta el 27 de abril.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Seguir leyendo →

Árbol de cadenas

José A. Alonso---0 Comentarios

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)]

Soluciones

  • Las soluciones se pueden escribir en los comentarios hasta el 26 de abril.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Seguir leyendo →

Sucesión de cubos perfectos

José A. Alonso---1 Comentario

Definir la lista

   sucesion :: [Integer]

cuyos elementos son los términos de la sucesión

   107811/3, 110778111/3, 111077781111/3, 111107777811111/3, ...

Por ejemplo,

   λ> take 5 sucesion
   [35937,36926037,37025927037,37035925937037,37036925926037037]
   λ> length (show (sucesion2 !! (3*10^6)))
   9000005

Comprobar con QuickCheck que todos los términos de la sucesión son cubos perfectos.

Soluciones

  • Las soluciones se pueden escribir en los comentarios hasta el 23 de abril.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Seguir leyendo →

Enlaces primos

José A. Alonso---2 Comentarios

Un enlace primo de longitud n es una permutación de 1, 2, …, n comienza con 1 y termina con n, tal que la suma de cada par de términos adyacentes es primo. Por ejemplo, para n = 6 la lista [1,4,3,2,5,6] es un enlace primo ua que las sumas de los pares de términos adyacentes son los números primos 5, 7, 5, 7, 11.

Definir la función

   enlacesPrimos :: Int -> [[Int]]

tal que (enlacesPrimos n) es la lista de los enlaces primos de longitud n. Por ejemplo,

   λ> enlacesPrimos 6
   [[1,4,3,2,5,6]]
   λ> enlacesPrimos 7
   [[1,4,3,2,5,6,7],[1,6,5,2,3,4,7]]
   λ> enlacesPrimos 8
   [[1,2,5,6,7,4,3,8],[1,4,7,6,5,2,3,8],[1,2,3,4,7,6,5,8],[1,6,7,4,3,2,5,8]]
   λ> length (enlacesPrimos 10)
   24
   λ> length (head (enlacesPrimos (5*10^4)))
   50000

Soluciones

import Data.List (permutations, delete)
import Data.Numbers.Primes (isPrime)
 
-- 1ª solución
-- ===========
 
enlacesPrimos :: Int -> [[Int]]
enlacesPrimos 1 = [[1]]
enlacesPrimos n =
  [ys | xs <- permutations [2..n-1],
       let ys = (1:xs)++[n],
       conEnlacesPrimos ys]
 
-- (conEnlacesPrimos xs) se verifica si las sumas de los elementos
-- adyacentes de xs son primos. Por ejemplo,
--    conEnlacesPrimos [1,4,3,2,5,6]  ==  True
--    conEnlacesPrimos [1,3,4,2,5,6]  ==  False
conEnlacesPrimos :: [Int] -> Bool
conEnlacesPrimos xs =
  all isPrime (enlaces xs)
 
-- (enlaces xs) es la lista de las sumas de los elementos adyacentes de
-- xs. Por ejemplo,
--    enlaces [1,4,3,2,5,6]  ==  [5,7,5,7,11]
--    enlaces [1,3,4,2,5,6]  ==  [4,7,6,7,11]
enlaces :: [Int] -> [Int]
enlaces xs =
  zipWith (+) xs (tail xs)
 
-- 2ª solución
-- ===========
 
enlacesPrimos2 :: Int -> [[Int]]
enlacesPrimos2 1 = [[1]]
enlacesPrimos2 n = aux [(n-1,[n],[n-1,n-2..2])]
  where
    aux [] = []
    aux ((1,x:xs,_):ts) =
      [1:x:xs | isPrime (1+x)] ++ aux ts
    aux ((k,x:xs,ys):ts) =
      aux ([(k-1,y:x:xs,delete y ys) | y <-ys, isPrime (y+x)] ++ ts)
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (enlacesPrimos 12)
--    216
--    (6.04 secs, 22,266,444,408 bytes)
--    λ> length (enlacesPrimos2 12)
--    216
--    (0.03 secs, 18,102,192 bytes)
--
--    λ> length (enlacesPrimos2 17)
--    59448
--    (2.69 secs, 8,514,104,800 bytes)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Seguir leyendo →

Raíces digitales de sucesiones de raíces digitales

José A. Alonso---5 Comentarios

La raíz digital de un número entero positivo n es el dígito que resulta al sumar sus dígitos, volviendo a sumar reiteradamente los resultados de esa suma y de las siguientes hasta que la suma sea un número de un dígito, al que se llama la raíz digital del número n y se representa pod D(n). Por ejemplo, la raíz digital del número 2345 es 6, porque 2+3+4+5+1 = 15 y sumando los dígitos del 15 resulta 6.

La sucesión de las raices digitales definida por un número a es la sucesión a(n) tal que a(0) = a y a(n+1) es la suma de a(n) y la raíz dígital de a(n). Por ejemplo, los primeros términos de la sucesión de las raíces digitales definida por 1 son

   1,2,4,8,16,23,28,29,31,35,43,50,55,56,58,62,70,77,82,83,85,89,...

Definir la función

   raicesDigitalesSucesionRaicesDigitales :: Integer -> [Integer]

tal que (raicesDigitalesSucesionRaicesDigitales a) es la lista de las raíces digitales de los elementos de la sucesión de raíces digitales definidas por a. Por ejemplo,

   λ> take 20 (raicesDigitalesSucesionRaicesDigitales 1)
   [1,2,4,8,7,5,1,2,4,8,7,5,1,2,4,8,7,5,1,2]
   λ> take 20 (raicesDigitalesSucesionRaicesDigitales 2021)
   [5,1,2,4,8,7,5,1,2,4,8,7,5,1,2,4,8,7,5,1]
   λ> raicesDigitalesSucesionRaicesDigitales (9^100) !! (10^9)
   9

Soluciones

import Data.List (cycle)
 
-- 1ª solución
-- ===========
 
raicesDigitalesSucesionRaicesDigitales :: Integer -> [Integer]
raicesDigitalesSucesionRaicesDigitales a =
  map raizDigital (sucesionRaicesDigitales a)
 
-- (sucesionRaicesDigitales a) es la sucesión de las raíces digitales
-- definida por un número a. Por ejemplo,
--    λ> take 22 (sucesionRaicesDigitales 1)
--    [1,2,4,8,16,23,28,29,31,35,43,50,55,56,58,62,70,77,82,83,85,89]
--    λ> take 22 (sucesionRaicesDigitales 3)
--    [3,6,12,15,21,24,30,33,39,42,48,51,57,60,66,69,75,78,84,87,93,96]
--    λ> take 22 (sucesionRaicesDigitales 5)
--    [5,10,11,13,17,25,32,37,38,40,44,52,59,64,65,67,71,79,86,91,92,94]
--    λ> take 22 (sucesionRaicesDigitales 7)
--    [7,14,19,20,22,26,34,41,46,47,49,53,61,68,73,74,76,80,88,95,100,101]
--    λ> take 22 (sucesionRaicesDigitales 9)
--    [9,18,27,36,45,54,63,72,81,90,99,108,117,126,135,144,153,162,171,180,189,198]
sucesionRaicesDigitales :: Integer -> [Integer]
sucesionRaicesDigitales a =
  iterate siguienteRaizDigital a
 
-- (siguienteRaizDigital a) es el siguiente de a en la sucesión de raices
-- digitales. Por ejemplo,
--    siguienteRaizDigital 23 == 28
siguienteRaizDigital :: Integer -> Integer
siguienteRaizDigital a =
  a + raizDigital a
 
-- (raizDigital n) es la raíz digital de n. Por ejemplo,
--    raizDigital 23451  ==  6
raizDigital :: Integer -> Integer
raizDigital n = 1 + (n-1) `mod` 9
 
-- (noPertenece x ys) se verifica si x no pertenece a la lista infinita
-- ordenada creciente ys. Por ejemplo,
--    noPertenece 2 [1,3..] == True
--    noPertenece 5 [1,3..] == False
noPertenece :: Integer -> [Integer] -> Bool
noPertenece x ys =
  not (x `pertenece` ys)
 
-- (Pertenece x ys) se verifica si x pertenece a la lista infinita
-- ordenada creciente ys. Por ejemplo,
--    pertenece 5 [1,3..] == True
--    pertenece 2 [1,3..] == False
pertenece :: Integer -> [Integer] -> Bool
pertenece x ys =
  x == head (dropWhile (<x) ys)
 
-- 2ª solución
-- ===========
 
-- En el ejercicio aterior vimos que sólo hay 5 sucesiones de ríace
-- digitales: las generadas por 1, 3, 5, 7 y 9. Las raíces digitales de
-- dichas sucesiones son
--    λ> take 20 (raicesDigitalesSucesionRaicesDigitales 1)
--    [1,2,4,8,7,5,1,2,4,8,7,5,1,2,4,8,7,5,1,2]
--    λ> take 20 (raicesDigitalesSucesionRaicesDigitales 3)
--    [3,6,3,6,3,6,3,6,3,6,3,6,3,6,3,6,3,6,3,6]
--    λ> take 20 (raicesDigitalesSucesionRaicesDigitales 5)
--    [5,1,2,4,8,7,5,1,2,4,8,7,5,1,2,4,8,7,5,1]
--    λ> take 20 (raicesDigitalesSucesionRaicesDigitales 7)
--    [7,5,1,2,4,8,7,5,1,2,4,8,7,5,1,2,4,8,7,5]
--    λ> take 20 (raicesDigitalesSucesionRaicesDigitales 9)
--    [9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]
-- Se observa que todas son periódicas.
 
raicesDigitalesSucesionRaicesDigitales2 :: Integer -> [Integer]
raicesDigitalesSucesionRaicesDigitales2 a =
  cycle (d : takeWhile (/= d) (tail (raicesDigitalesSucesionRaicesDigitales a)))
  where d = raizDigital a
 
-- 3ª solución
-- ===========
 
raicesDigitalesSucesionRaicesDigitales3 :: Integer -> [Integer]
raicesDigitalesSucesionRaicesDigitales3 a =
  case (raizDigital a) of
    1 -> cycle [1,2,4,8,7,5]
    2 -> cycle [2,4,8,7,5,1]
    3 -> cycle [3,6]
    4 -> cycle [4,8,7,5,1,2]
    5 -> cycle [5,1,2,4,8,7]
    6 -> cycle [6,3]
    7 -> cycle [7,5,1,2,4,8]
    8 -> cycle [8,7,5,1,2,4]
    9 -> cycle [9]
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> raicesDigitalesSucesionRaicesDigitales (9^100) !! (3*10^6)
--    9
--    (4.23 secs, 2,160,860,128 bytes)
--    λ> raicesDigitalesSucesionRaicesDigitales2 (9^100) !! (3*10^6)
--    9
--    (0.02 secs, 103,768 bytes)
--    λ> raicesDigitalesSucesionRaicesDigitales3 (9^100) !! (3*10^6)
--    9
--    (0.02 secs, 103,056 bytes)
--
--    λ> raicesDigitalesSucesionRaicesDigitales2 (9^100) !! (10^9)
--    9
--    (2.09 secs, 103,608 bytes)
--    λ> raicesDigitalesSucesionRaicesDigitales3 (9^100) !! (10^9)
--    9
--    (2.25 secs, 102,952 bytes)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Seguir leyendo →

Sucesiones de raíces digitales

José A. Alonso---1 Comentario

La raíz digital de un número entero positivo n es el dígito resulta al sumar sus dígitos, volviendo a sumar reiteradamente resultados de esa suma y de las siguientes hasta que la suma sea un número de un dígito, al que se llama la raíz digital del número n y se representa pod D(n). Por ejemplo, la raíz digital del número 23451 es 6, porque 2+3+4+5+1 = 15 y sumando los dígitos del 15 resulta 6.

La sucesión de las raices digitales definida por un número a es la sucesión a(n) tal que a(0) = a y a(n+1) es la suma de a(n) y la raíz dígital de a(n). Por ejemplo, los primeros términos de la sucesión de las raíces digitales definida por 1 son

   1,2,4,8,16,23,28,29,31,35,43,50,55,56,58,62,70,77,82,83,85,89,...

Se observa que el menor número que no pertenece a la sucesión anterior es 3. Los primeros términos de la sucesión de las raíces digitales definida por 3 son

   3,6,12,15,21,24,30,33,39,42,48,51,57,60,66,69,75,78,84,87,93,96,...

Se observa que el menor número que no pertenece a las 2 sucesiones anteriores es 5. Los primeros términos de la sucesión de las raíces digitales definida por 5 son

   5,10,11,13,17,25,32,37,38,40,44,52,59,64,65,67,71,79,86,91,92,94,...

Definir la función

   sucesionSucesionesRaicesDigitales :: [[Integer]]

tal que sus elementos son las sucesiones de raíces digitales tal el primer elemento de cada sucesión es el menor elemento que no pertenece a las sucesiones anteriores. Por ejemplo,

   λ> map (take 5) (take 4 sucesionSucesionesRaicesDigitales)
   [[1,2,4,8,16],[3,6,12,15,21],[5,10,11,13,17],[7,14,19,20,22]]

Comprobar con QuickCheck que sucesionSucesionesRaicesDigitales tiene exactamente 5 elementos.

Soluciones

import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
sucesionSucesionesRaicesDigitales :: [[Integer]]
sucesionSucesionesRaicesDigitales =
  map aux [1..]
  where aux 1 = sucesionRaicesDigitales 1
        aux n = sucesionRaicesDigitales m
          where m = head [a | a <- [1..],
                              all (a `noPertenece`)
                                  [aux k | k <- [1..n-1]]]
 
-- (sucesionRaicesDigitales a) es la sucesión de las raíces digitales
-- definida por un número a. Por ejemplo,
--    λ> take 22 (sucesionRaicesDigitales 1)
--    [1,2,4,8,16,23,28,29,31,35,43,50,55,56,58,62,70,77,82,83,85,89]
--    λ> take 22 (sucesionRaicesDigitales 3)
--    [3,6,12,15,21,24,30,33,39,42,48,51,57,60,66,69,75,78,84,87,93,96]
--    λ> take 22 (sucesionRaicesDigitales 5)
--    [5,10,11,13,17,25,32,37,38,40,44,52,59,64,65,67,71,79,86,91,92,94]
--    λ> take 22 (sucesionRaicesDigitales 7)
--    [7,14,19,20,22,26,34,41,46,47,49,53,61,68,73,74,76,80,88,95,100,101]
--    λ> take 22 (sucesionRaicesDigitales 9)
--    [9,18,27,36,45,54,63,72,81,90,99,108,117,126,135,144,153,162,171,180,189,198]
sucesionRaicesDigitales :: Integer -> [Integer]
sucesionRaicesDigitales a =
  iterate siguienteRaizDigital a
 
-- (siguienteRaizDigital a) es el siguiente de a en la sucesión de raices
-- digitales. Por ejemplo,
--    siguienteRaizDigital 23 == 28
siguienteRaizDigital :: Integer -> Integer
siguienteRaizDigital a =
  a + raizDigital a
 
-- (raizDigital n) es la raíz digital de n. Por ejemplo,
--    raizDigital 23451  ==  6
raizDigital :: Integer -> Integer
raizDigital n = 1 + (n-1) `mod` 9
 
-- (noPertenece x ys) se verifica si x no pertenece a la lista infinita
-- ordenada creciente ys. Por ejemplo,
--    noPertenece 2 [1,3..] == True
--    noPertenece 5 [1,3..] == False
noPertenece :: Integer -> [Integer] -> Bool
noPertenece x ys =
  not (x `pertenece` ys)
 
-- (Pertenece x ys) se verifica si x pertenece a la lista infinita
-- ordenada creciente ys. Por ejemplo,
--    pertenece 5 [1,3..] == True
--    pertenece 2 [1,3..] == False
pertenece :: Integer -> [Integer] -> Bool
pertenece x ys =
  x == head (dropWhile (<x) ys)
 
-- 2ª solución
-- ===========
 
sucesionSucesionesRaicesDigitales2 :: [[Integer]]
sucesionSucesionesRaicesDigitales2 = aux [1..]
  where aux xs = sucesion xs : aux (diferencia xs (sucesion xs))
        sucesion xs = sucesionRaicesDigitales (head xs)
 
-- (diferencia xs ys) es la diferencia las listas infinitas ordenadas
-- crecientes xs e ys. Por ejemplo,
--    λ> take 8 (diferencia [1..] [2,4..])
--    [1,3,5,7,9,11,13,15]
diferencia :: [Integer] -> [Integer] -> [Integer]
diferencia (x:xs) (y:ys)
  | x == y    = diferencia xs ys
  | otherwise = x : diferencia xs (y:ys)
 
-- Propiedad
-- =========
 
-- Del cálculo 
--    λ> map (take 4) (take 5 sucesionSucesionesRaicesDigitales)
--    [[1,2,4,8],[3,6,12,15],[5,10,11,13],[7,14,19,20],[9,18,27,36]]
-- se deduce que tiene al menos 5. Sólo queda por comprobar que no tiene más; es decir
prop_sucesionSucesionesRaicesDigitales :: Integer -> Property
prop_sucesionSucesionesRaicesDigitales n =
  n > 0 ==>
  any (n `pertenece`) xss
  where xss = take 5 (sucesionSucesionesRaicesDigitales2)
 
-- La comprobación es
--    λ> quickCheck prop_sucesionSucesionesRaicesDigitales
--    +++ OK, passed 100 tests.

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Seguir leyendo →

Raíces digitales de los números de Fibonacci

José A. Alonso---1 Comentario

La sucesión Fibonacci es la siguiente sucesión infinita de números naturales:

   1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

La sucesión comienza con los números 1 y 1 y, a partir de estos, cada término es la suma de los dos anteriores.

Definir la función

   raizDigitalFibonacci :: Integer -> Integer

tal que (raizDigitalFibonacci n) es la raíz digital del n-ésimo número de Fibonacci. Por ejemplo,

   raizDigitalFibonacci 6         ==  4
   raizDigitalFibonacci 7         ==  3
   raizDigitalFibonacci (3*10^7)  ==  1

Soluciones

import Data.List (genericIndex, cycle)
 
-- 1ª solución
-- ===========
 
raizDigitalFibonacci :: Integer -> Integer
raizDigitalFibonacci =
  raizDigital . fibonacci
 
-- (fibonacci k) es el k-ésimo número de Fibonacci. Por ejemplo,
fibonacci :: Integer -> Integer
fibonacci 0 = 1
fibonacci 1 = 1
fibonacci n = fibonacci (n-1) + fibonacci (n-2)
 
-- (raizDigital n) es la raíz digital de n. Por ejemplo,
--    raizDigital 23451  ==  6
raizDigital :: Integer -> Integer
raizDigital n = 1 + (n-1) `mod` 9
 
-- 2ª solución
-- ===========
 
raizDigitalFibonacci2 :: Integer -> Integer
raizDigitalFibonacci2 n =
  raizDigital (fibs `genericIndex` n)
 
-- fibs es la la sucesión de los números de Fibonacci. Por ejemplo,
--    take 14 fibs  == [1,1,2,3,5,8,13,21,34,55,89,144,233,377]
fibs :: [Integer]
fibs = 1 : scanl (+) 1 fibs
 
-- 3ª solución
-- ===========
 
-- En el cálculo
---   λ> map raizDigitalFibonacci2 [0..47]
---   [1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9,
--     1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9]
-- se observa que la lista es periódica con período
--    1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9,
 
raizDigitalFibonacci3 :: Integer -> Integer
raizDigitalFibonacci3 n =
  raicesDigitalesFibonacci `genericIndex` n
 
-- raicesDigitalesFibonacci es la suceción de las raíces digitales de
-- los números de Fibonacci. Por ejemplo,
---   λ> take 24 raicesDigitalesFibonacci
---   [1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9]
raicesDigitalesFibonacci :: [Integer]
raicesDigitalesFibonacci =
  concat (repeat [1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9])
 
-- 4ª solución
-- ===========
 
raizDigitalFibonacci4 :: Integer -> Integer
raizDigitalFibonacci4 n =
  raicesDigitalesFibonacci2 `genericIndex` n
 
-- raicesDigitalesFibonacci2 es la suceción de las raíces digitales de
-- los números de Fibonacci. Por ejemplo,
---   λ> take 24 raicesDigitalesFibonacci2
---   [1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9]
raicesDigitalesFibonacci2 :: [Integer]
raicesDigitalesFibonacci2 =
  cycle [1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9]
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> raizDigitalFibonacci 34
--    8
--    (7.88 secs, 3,560,871,624 bytes)
--    λ> raizDigitalFibonacci2 34
--    8
--    (0.01 secs, 106,896 bytes)
--    λ> raizDigitalFibonacci3 34
--    8
--    (0.01 secs, 106,568 bytes)
--    λ> raizDigitalFibonacci4 34
--    8
--    (0.01 secs, 107,512 bytes)
--
--    λ> raizDigitalFibonacci2 (4*10^5)
--    4
--    (3.19 secs, 7,146,227,192 bytes)
--    λ> raizDigitalFibonacci3 (4*10^5)
--    4
--    (0.05 secs, 80,635,064 bytes)
--    λ> raizDigitalFibonacci4 (4*10^5)
--    4
--    (0.05 secs, 57,701,392 bytes)
--
--    λ> raizDigitalFibonacci3 (10^7)
--    4
--    (1.34 secs, 2,013,435,912 bytes)
--    λ> raizDigitalFibonacci4 (10^7)
--    4
--    (0.66 secs, 1,440,100,712 bytes)
--
--    λ> raizDigitalFibonacci4 (3*10^7)
--    1
--    (1.92 secs, 4,320,102,368 bytes)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Seguir leyendo →

Raíces digitales de los números de Fermat.

José A. Alonso---1 Comentario

Los números de Fermat son los número de la forma F(n) = 2^(2^n) + 1, donde n es un número natural.

Definir la función

   raizDigitalFermat :: Integer -> Integer

tal que (raizDigitalFermat n) es la raíz digital del n-ésimo número de Fermat. Por ejemplo,

   raizDigitalFermat 3          ==  5
   raizDigitalFermat (10^2021)  ==  8

Soluciones

-- 1ª solución
-- ===========
 
raizDigitalFermat :: Integer -> Integer
raizDigitalFermat =
  raizDigital . fermat
 
-- (fermat k) es el k-ésimo número de Fermat. Por ejemplo,
--    fermat 0  ==  3
--    fermat 1  ==  5
--    fermat 2  ==  17
--    fermat 3  ==  257
--    fermat 4  ==  65537
--    fermat 5  ==  4294967297
fermat :: Integer -> Integer
fermat k = 1 + 2^(2^k)
 
-- (raizDigital n) es la raíz digital de n. Por ejemplo,
--    raizDigital 23451  ==  6
raizDigital :: Integer -> Integer
raizDigital n = 1 + (n-1) `mod` 9
 
-- 2ª solución
-- ===========
 
-- En el cálculo
--    λ> map raizDigitalFermat [0..20]
--    [3,5,8,5,8,5,8,5,8,5,8,5,8,5,8,5,8,5,8,5,8]
-- se observa que se compone del 3 seguido por la repetición periódica
-- de 5 y 8.
 
raizDigitalFermat2 :: Integer -> Integer
raizDigitalFermat2 0 = 3
raizDigitalFermat2 n
  | odd n     = 5
  | otherwise = 8
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> raizDigitalFermat 30
--    8
--    (6.76 secs, 536,981,128 bytes)
--    λ> raizDigitalFermat2 30
--    8
--    (0.01 secs, 98,400 bytes)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Seguir leyendo →