Menu Close

Números fibonaccianos

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

import Data.List (inits, isPrefixOf, sort)
 
-- Definición de esFibonacciano
-- ============================
 
esFibonacciano :: Integer -> Bool
esFibonacciano n =
  n > 99 && ds `isPrefixOf` drop 2 fs
  where (a:b:ds) = digitos n
        fs = a : b : zipWith (+) fs (tail fs)
 
-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 325  ==  [3,2,5]
digitos :: Integer -> [Int]
digitos n =
  [read [c] | c <- show n]
 
-- 1ª definición de fibonaccianos
-- ==============================
 
fibonaccianos :: [Integer]
fibonaccianos =
  filter esFibonacciano [100..10112358]
 
-- 2ª definición de fibonaccianos
-- ==============================
 
fibonaccianos2 :: [Integer]
fibonaccianos2 =
  sort (concat [aux a b | a <- [1..9], b <- [0..9]])
  where
    aux a b = [digitosAnumero zs | zs <- drop 3 (inits (takeWhile (<10) (fibs a b)))]
 
-- (fibs a b) es la sucesión de números de Fibonacci cuyos dos primeros
-- términos son a y b. Por ejemplo,
--    take 9 (fibs 2 4)  ==  [2,4,6,10,16,26,42,68,110]
--    take 9 (fibs 3 6)  ==  [3,6,9,15,24,39,63,102,165]
fibs :: Integer -> Integer -> [Integer]
fibs a b = fs
  where fs = a : b : zipWith (+) fs (tail fs)
 
-- (digitosAnumero xs) es el número cuya lista de dígitos es xs. Por
-- ejemplo,
--    digitosAnumero [8,1,6,4,9]  ==  81649
digitosAnumero :: [Integer] -> Integer
digitosAnumero xs =
  read (concatMap show xs)
 
-- fibonaccianosG
-- ==============
 
fibonaccianosG :: Integer -> [Integer]
fibonaccianosG n =
  sort (concat [fibonaccianosGAux n a b | a <- [1..9], b <- [0..9]])
 
fibonaccianosGAux :: Integer -> Integer -> Integer -> [Integer]
fibonaccianosGAux n a b =
  [digitosAnumero zs | zs <- drop 3 (inits (takeWhile (<n) (fibs a b)))]
 
-- Comprobación de la generalización
--    λ> fibonaccianos2 == fibonaccianosG 10
--    True
 
--    λ> length (fibonaccianosG (10^40))
--    16888
--    (2.41 secs, 10,546,873,616 bytes)
--    λ> length (show (last (fibonaccianosG (10^40))))
--    3943
--    (2.41 secs, 10,547,101,856 bytes)
 
-- Cálculos
-- ========
 
-- El cálculo del máximo número de cifras de los números fibonaccianos
-- es
--      λ> maximum [length (show n) | n <- fibonaccianos2]
--      8
--      λ> length (show (last fibonaccianos2))
--      8
 
-- El cálculo de la cantidad de números fibonaccianos es
--      λ> length fibonaccianos2
--      84

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>
Ejercicio

2 soluciones de “Números fibonaccianos

  1. Joaquín Infante Rodríguez
    import Data.List
     
    --Antes que nada definimos dos funciones auxiliares que nos van a ser de gran
    --ayuda. Las hemos usado ya tantas veces que considero que no precisan ni
    --explicación previa.
     
    listaNumero :: [Integer] -> Integer
    listaNumero []     = 0
    listaNumero (x:xs) = x*10^(genericLength xs) + listaNumero xs
     
    digitos :: Integer -> [Integer]
    digitos n = [read[x] | x<-show n]
     
     
    --Veamos ahora la definición de esFibonaccianaL, tal que esFibonaccianaL xs
    --determina si la lista xs es fibonacciana, adaptando la definición del
    --enunciado a listas. Es decir, si la lista tiene longitud mayor o igual que 3
    --(como es el caso base es necesario que sea True, aunque no es cierto. Esto no
    --afectará a los números fibonaccianos, pues tienen tres o más cifras) y si
    --cada cifra se obtiene sumando las dos anteriores.
    --  Por ejemplo: esFibonaccianaL [1,1,2,3] == True  (0.00 secs, 56,856 bytes)
    --               esFibonaccianaL [1,1,2,1] == False (0.00 secs, 61,184 bytes)
     
    esFibonaccianaL :: [Integer] -> Bool
    esFibonaccianaL xs@(x:y:z:ys) | length xs < 3       = True
                                  | null ys && z == x+y = True
                                  | otherwise           = (z==x+y) && esFibonaccianaL (y:z:ys)
     
    --Una vez que ya tenemos definida la función esFibonaccianaL, es trivial
    --definir la función esFibonacciano, tal que esFibonacciano n devuelve True si
    --n es fibonacciano (es decir, si sus dígitos forman una lista fibonacciana).
    --Por ejemplo:  esFibonacciano 5279 == True  (0.02 secs, 73,688 bytes)
    --              esFibonacciano 1121 == False (0.02 secs, 73,856 bytes)
     
    esFibonacciano :: Integer -> Bool
    esFibonacciano n = esFibonaccianaL (digitos n)
     
    --Definimos la lista constante primerosNFibonaccianos, la cual nos devuelve la
    --lista de los números fibonaccianos que se encuentran en el rango [100,1000].
    --   ghci>  primerosNFibonaccianos ==
    --          [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]
    --           (0.02 secs, 11,231,360 bytes)
    --   ghci>  length primerosNFibonaccianos == 45 (0.02 secs, 55,648 bytes)
     
    primerosNFibonaccianos :: [Integer]
    primerosNFibonaccianos = [x | x<-[(10^2)..(10^3)], esFibonacciano x]
     
    --A partir de aquí, entramos en la parte interesante del problema. Todo número
    --fibonacciano queda perfectamente definido por sus dos primeras cifras, es
    --decir, si el número empieza por 23, la siguiente cifra tiene que ser 5
    --obligatoriamente. Repitiendo el razonamiento, la siguiente cifra deberá ser el
    --8. Y aquí paramos, pues la siguiente sería (5+8)=13, la cual no es una cifra
    --válida para construir otro número, luego el número fibonacciano definido por
    --23 es y solo es el 2358.
    --Por tanto, como hemos calculado previamente todos los números fibonaccianos
    --de tres cifras en primerosNFibonaccianos, solo tendremos que trabajar con
    --estos 45 números, lo cual mejorará considerablemente la eficiencia del programa.
    --Con la función constante ampliacion lo que llevamos a cabo es añadir la siguiente cifra
    --a los elementos de primerosNFibonaccianos, usando aux1, la cual amplía
    --cualquier lista dada.
    --    ghci> ampliacion
    --          [1011,1123,1235,1347,1459,2022,2134,2246,2358,3033,3145,3257,3369,
    --           4044,4156,4268,5055,5167,5279,6066,6178,7077,7189,8088,9099]
    --           (0.03 secs, 25,691,200 bytes)
     
    ampliacion :: [Integer]
    ampliacion = aux1 (primerosNFibonaccianos)
     
    aux1 :: [Integer] -> [Integer] 
    aux1 xs = [listaNumero (digitos x ++ [y]) | x<-xs, y<-[0..9],
                     esFibonacciano (listaNumero (digitos x ++ [y]))]
     
    --Para finalizar, calculamos todos los números fibonaccianos con la función
    --constante nFibonaccianos, la cual se obtiene de iterar la funcion Aux1 en
    --primerosNFibonaccianos (hemos usado la auxiliar iteraAux1, la cual itera aux1
    --en cualquier lista xs dada).
     
    nFibonaccianos :: [Integer]
    nFibonaccianos = iteraAux1 (primerosNFibonaccianos)
     
    iteraAux1 :: [Integer] -> [Integer]
    iteraAux1 [] = []
    iteraAux1 xs = nub (xs ++ aux1 xs ++ iteraAux1 (aux1 xs)) 
     
    --Luego, vemos que los números fibonaccianos son:
    --   ghci>  nFibonaccianos ==
    --          [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,4268,5055,5167,5279,6066,6178,7077,7189,8088,9099,10112,11235,
    --           12358,20224,21347,30336,31459,40448,101123,112358,202246,303369,1011235,10112358]
    --           (0.05 secs, 77,522,592 bytes)
     
    --   ghci>  length nFibonaccianos == 84 (0.00 secs, 59,792 bytes)
     
    --   ghci>  maximum nFibonaccianos == 10112358 (0.00 secs, 63,664 bytes)
     
    --   ghci>  length (show (maximum nFibonaccianos)) == 8 (0.04 secs, 77,252,312 bytes)
     
    --Respondiendo a las preguntas que nos hacían, queda por tanto demostrado que
    --solo existen 84 números fibonaccianos, siendo el de mayor número de cifras
    --el 10112358 (el cual tiene 8 cifras).
     
     
    --Como un extra, podemos analizar y razonar por qué el número 10112358 es el
    --mayor número fibonacciano.
    --Como hemos dicho, todo número fibonacciano queda perfectamente definido por
    --sus dos primeras cifras, luego bastará observar estas.
    --La primera cifra no puede ser un 0, pues entonces no sería máximo, el número
    --01212==1212; luego queda descartado.
    -- Por tanto, la primera cifra deberá ser un 1 y la segunda un 0, para que al
    --realizar las sucesivas sumas, estas crezcan lo más lento posible y así llegar
    --al mayor número de cifras.
    -- En conclusión:
     
    -- 10  ==>  101  ==> 1011  ==> 10112 ==> 101123 ==> 1011235 ==> 10112358 ==> 10112358(13) !!! ABSURDO
    --ya que 13 no es una cifra válida. Luego 10112358 es el mayor número fibonacciano.
     
     
    --Comentario: Realicé el ejercicio propuesto justo el día antes de que se
    --publicase en el blog y lo mandé al correo de la RSME, para hacer este
    --ejercicio, mantendré el ejercicio original y a partir de aquí, realizaré lo
    --que se ha añadido en el enunciado del blog, es decir, los números
    --fibonaccianos generalizados.
     
    --La función tomarDeNenN, separa una lista de dígitos (números del 0 al 9)
    --según el valor que introduzcamos en n.
    --Por ejemplo:   ghci> tomarDeNenN 2 [5,7,1,2,1,9,3,1,5,0,8,1] ==
    --                     [57,12,19,31,50,81] (0.02 secs, 81,232 bytes)
     
    tomarDeNenN :: Integer -> [Integer] -> [Integer]
    tomarDeNenN n [] = []
    tomarDeNenN n xs = [listaNumero (genericTake n xs)] ++ tomarDeNenN n (genericDrop n xs)
     
     
    --Análogamente a la definición de números fibonaccianos normal, definimos la
    --función esFibonaccianaLG, tal que dada una lista de enteros, determina si esa
    --lista es fibonaccianaG o no, siguiendo la definición del enunciado y haciendo
    --uso de la auxiliar tomarDeNenN.
    -- Por ejemplo:   ghci> esFibonaccianaLG 100 [5,7,1,2,1,9,3,1,5,0,8,1] == True
    --                                                               (0.00 secs, 71,920 bytes)
    --                ghci> esFibonaccianaLG 100 [5,7,1,2,1,9,3,1,5,0,8,2] == False
    --                                                               (0.00 secs, 72,240 bytes)
     
    esFibonaccianaLG :: Integer -> [Integer] -> Bool
    esFibonaccianaLG n xs@(x:y:ys) = all (<n) zs &&  esFibonaccianaL zs
                                where aux1 = x+y   
                                      long = genericLength (digitos aux1)
                                      zs   = (x:y:(tomarDeNenN (long) ys))
     
     
    --Una vez que ya tenemos definida la función esFibonaccianaLG, es trivial
    --definir la función esFibonaccianoG, tal que esFibonaccianoG n devuelve True si
    --n es fibonaccianoG (es decir, si sus dígitos forman una lista fibonacciana generalizada).
    --Por ejemplo:  esFibonaccianoG 100 571219315081 == True (0.00 secs, 118,504 bytes)
    --              esFibonaccianoG 10  1121 == False (0.00 secs, 73,856 bytes)
     
    esFibonaccianoG :: Integer -> Integer -> Bool
    esFibonaccianoG n x = esFibonaccianaLG n (digitos x)
     
    --Los primerosNFibonaccianosG, es la lista constante que devuelve los
    --números fibonaccianos generalizados acotados por n en el rango [1000,10000]
    --más la lista constante primerosNFibonaccianos.
    --  ghci> primerosNFibonaccianosG 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]
    --        (0.03 secs, 13,412,280 bytes)
     
    primerosNFibonaccianosG :: Integer -> [Integer]
    primerosNFibonaccianosG n = sort $primerosNFibonaccianos ++ [x | x<-[(10^3)..(10^4)], esFibonaccianoG n x]
     
    --Podemos ampliar los razonamientos anteriores y obtenemos funciones análogas
    --de los números fibonaccianos para los números fibonaccianos generalizados:
     
    ampliacionG :: Integer -> [Integer]
    ampliacionG n = sort $ aux4 n (primerosNFibonaccianosG n)
     
     
    aux4 :: Integer -> [Integer] -> [Integer] 
    aux4 n xs = [listaNumero (digitos x ++ (digitos y)) | x<-xs, y<-[0..n],
                     esFibonaccianoG n (listaNumero (digitos x ++ (digitos y)))]
     
    nFibonaccianosG :: Integer -> [Integer]
    nFibonaccianosG n = sort $ iteraAux4 n (primerosNFibonaccianosG n)
     
    iteraAux4 :: Integer -> [Integer] -> [Integer]
    iteraAux4 n [] = []
    iteraAux4 n xs = nub (xs ++ aux4 n xs ++ iteraAux4 n (aux4 n xs))
     
      --  ghci> take 60 (nFibonaccianosG 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]
    --           (4.93 secs, 6,820,672,848 bytes)
     
    --    ghci>  take 12 (drop 60 (nFibonaccianosG 100)) == 
    --            [3369,3710,3811,3912,4044,4156,4268,4610,4711,4812,4913,5055]
    --            (4.76 secs, 6,820,538,088 bytes)
     
    --    ghci>  take 12 (drop 60 (nFibonaccianosG 10)) == 
    --           [4268,5055,5167,5279,6066,6178,7077,7189,8088,9099,10112,11235]
    --           (0.21 secs, 311,142,816 bytes)
     
     
    --NOTA : LA PRIMERA PARTE DEL PROBLEMA (NÚMEROS FIBONACCIANOS) ES REALMENTE
    --EFICIENTE, PUDIENDO CALCULAR EL EJERCICIO EN SOLO 0.05 SECS. PARA LOS
    --GENERALIZADOS NO HE CONSEGUIDO OBTENER UNA FUNCIÓN QUE SE APROVECHE AL MÁXIMO
    --DE LAS SUMAS DE LOS ANTERIORES TÉRMINOS, CONSIGUIENDO CALCULAR LOS PRIMEROS
    --CASOS PERO NO LLEGANDO NI DE LEJOS A LOS CASOS MUY MUY GRANDES.
  2. María Ruiz
    import Data.List(inits)
     
    fibonaccianosG :: Integer -> [Integer]
    fibonaccianosG c =
      mezclaTodas [auxAcotado c n | n <-[10..99]]
     
    -- length (fibonaccianosG (10^40)) == 16888
    -- (2.45 secs, 10,897,434,840 bytes)
    -- length (show (last (fibonaccianosG (10^40)))) == 3943
    -- (2.44 secs, 10,897,661,688 bytes)
     
     
    auxAcotado :: Integer -> Integer -> [Integer]
    auxAcotado c n = map f $ drop 3 $ inits $ reverse $ until pred g as
      where pred (x:y:_) = x + y >= c
            f ys = read $ concatMap show ys
            as = reverse [read [x] | x <- show n]
            g (x:y:xs) = (x+y):x:y:xs     
     
    mezclaTodas :: Ord a => [[a]] -> [a]
    mezclaTodas = foldr mezcla []
     
    mezcla :: Ord a => [a] -> [a] -> [a]
    mezcla xs [] = xs
    mezcla [] ys = ys
    mezcla (x:xs) (y:ys) | x < y  = x : mezcla xs (y:ys)
                         | x == y = x : mezcla xs ys
                         | x > y  = y : mezcla (x:xs) ys
     
     
    fibonaccianos  :: [Integer]
    fibonaccianos = fibonaccianosG 10
     
     
    esFibonacciano :: Integer -> Bool
    esFibonacciano n = esFibL [read [x] | x <- show n]
      where esFibL (x:y:z:xs) = z == x+y && (null xs || esFibL (y:z:xs))
     
    -- length fibonaccianos == 84
    -- (0.00 secs, 66,336 bytes)
    -- all esFibonacciano fibonaccianos == True
    -- (0.01 secs, 1,348,864 bytes)

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.