Raíces digitales de los números de Fibonacci
La sucesión Fibonacci es la siguiente sucesión infinita de números naturales:
|
1 |
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
|
1 |
raizDigitalFibonacci :: Integer -> Integer |
tal que (raizDigitalFibonacci n) es la raíz digital del n-ésimo número de Fibonacci. Por ejemplo,
|
1 2 3 |
raizDigitalFibonacci 6 == 4 raizDigitalFibonacci 7 == 3 raizDigitalFibonacci (3*10^7) == 1 |
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 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
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>
Un comentario