Menu Close

Día: 21 abril, 2021

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>