Números de Pentanacci
Los números de Fibonacci se definen mediante las ecuaciones
|
1 2 3 |
F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2), si n > 1 |
Los primeros números de Fibonacci son
|
1 |
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... |
Una generalización de los anteriores son los números de Pentanacci definidos por las siguientes ecuaciones
|
1 2 3 4 5 6 |
P(0) = 0 P(1) = 1 P(2) = 1 P(3) = 2 P(4) = 4 P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4 |
Los primeros números de Pentanacci son
|
1 |
0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ... |
Definir la sucesión
|
1 |
pentanacci :: [Integer] |
cuyos elementos son los números de Pentanacci. Por ejemplo,
|
1 2 3 4 5 6 7 |
λ> take 15 pentanacci [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525] λ> (pentanacci !! (10^5)) `mod` (10^30) 482929150584077921552549215816 231437922897686901289110700696 λ> length (show (pentanacci !! (10^5))) 29357 |
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 |
import Data.List (zipWith5) import Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs) -- 1ª solución -- =========== pentanacci1 :: [Integer] pentanacci1 = [pent n | n <- [0..]] pent :: Integer -> Integer pent 0 = 0 pent 1 = 1 pent 2 = 1 pent 3 = 2 pent 4 = 4 pent n = pent (n-1) + pent (n-2) + pent (n-3) + pent (n-4) + pent (n-5) -- 2ª solución -- =========== pentanacci2 :: [Integer] pentanacci2 = 0 : 1 : 1 : 2 : 4 : zipWith5 f (r 0) (r 1) (r 2) (r 3) (r 4) where f a b c d e = a+b+c+d+e r n = drop n pentanacci2 -- 3ª solución -- =========== pentanacci3 :: [Integer] pentanacci3 = p (0, 1, 1, 2, 4) where p (a, b, c, d, e) = a : p (b, c, d, e, a + b + c + d + e) -- 4ª solución -- =========== pentanacci4 :: [Integer] pentanacci4 = 0: 1: 1: 2: 4: p pentanacci4 where p (a:b:c:d:e:xs) = (a+b+c+d+e): p (b:c:d:e:xs) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_pentanacci :: NonNegative Int -> Bool prop_pentanacci (NonNegative n) = all (== pentanacci1 !! n) [pentanacci1 !! n, pentanacci2 !! n, pentanacci3 !! n] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=25}) prop_pentanacci -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> pentanacci1 !! 25 -- 5976577 -- (3.18 secs, 1,025,263,896 bytes) -- λ> pentanacci2 !! 25 -- 5976577 -- (0.00 secs, 562,360 bytes) -- -- λ> length (show (pentanacci2 !! (10^5))) -- 29357 -- (1.04 secs, 2,531,259,408 bytes) -- λ> length (show (pentanacci3 !! (10^5))) -- 29357 -- (1.00 secs, 2,548,868,384 bytes) -- λ> length (show (pentanacci4 !! (10^5))) -- 29357 -- (0.96 secs, 2,580,065,520 bytes) |
El código se encuentra en GitHub.
Referencias
- Tito III Piezas y Eric Weisstein, Pentanacci number.
- N. J. A. Sloane, Sucesión A001591 de la OEIS.