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
1 2 3 |
esFibonacciano :: Integer -> Bool fibonaccianos :: [Integer] fibonaccianosG :: Integer -> [Integer] |
tales que
- (esFibonacciano n) se verifica si n es un número fibonacciano. Por ejemplo,
1 2 |
esFibonacciano 5279 == True esFibonacciano 527916 == False |
- fibonaccianos es la lista de los números fibonaccianos. Por ejemplo,
1 2 3 4 5 |
λ> 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,
1 2 3 4 5 6 7 8 9 10 11 12 13 |
λ> 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
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>