Cantidad de números Pentanacci impares
Los números de Pentanacci se definen mediante las 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, ... |
Se obseeva que
- hasta P(5) hay 1 impar: el 1 (aunque aparece dos veces);
- hasta P(7) hay 2 impares distintos: 1 y 31;
- hasta P(10) hay 3 impares distintos: 1, 31 y 61;
- hasta P(15) hay 5 impares distintos: 1, 31 y 61, 1793 y 3525.
Definir la función
|
1 |
nPentanacciImpares :: Integer -> Integer |
tal que (nPentanacciImpares n) es la cantidad de números impares distintos desde P(0) hasta P(n). Por ejemplo,
|
1 2 3 4 5 6 7 8 9 |
nPentanacciImpares 5 == 1 nPentanacciImpares 7 == 2 nPentanacciImpares 10 == 3 nPentanacciImpares 15 == 5 nPentanacciImpares 100 == 33 nPentanacciImpares 1000 == 333 nPentanacciImpares 10000 == 3333 nPentanacciImpares (10^(10^6)) `mod` (10^9) == 333333333 length (show (nPentanacciImpares2 (10^(10^6)))) == 1000000 |
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 |
import Data.List (genericLength, genericTake) -- 1ª definición -- ============= nPentanacciImpares1 :: Integer -> Integer nPentanacciImpares1 0 = 0 nPentanacciImpares1 1 = 1 nPentanacciImpares1 n = genericLength (filter odd (genericTake (n+1) pentanacci)) - 1 pentanacci :: [Integer] pentanacci = p (0, 1, 1, 2, 4) where p (a, b, c, d, e) = a : p (b, c, d, e, a + b + c + d + e) -- 2ª definición -- ============= -- λ> map nPentanacciImpares1 [1..31] -- [1,1,1,1,1,1,2,3,3,3,3,3,4,5,5,5,5,5,6,7,7,7,7,7,8,9,9,9,9,9,10] -- λ> [(head xs, length xs) | xs <- group (map nPentanacciImpares1 [1..37])] -- [(1,6),(2,1),(3,5),(4,1),(5,5),(6,1),(7,5),(8,1),(9,5),(10,1),(11,5),(12,1)] nPentanacciImpares2 :: Integer -> Integer nPentanacciImpares2 0 = 0 nPentanacciImpares2 1 = 1 nPentanacciImpares2 n = 2 * q + min r 2 - 1 where (q,r) = n `quotRem` 6 -- 3ª definición -- ============= nPentanacciImpares3 :: Integer -> Integer nPentanacciImpares3 0 = 0 nPentanacciImpares3 1 = 1 nPentanacciImpares3 n | r == 5 = 2*q + 2 | otherwise = 2*q + 1 where (q,r) = divMod (n-2) 6 |
Observamos que cada 6 términos de la sucesión, se repite la secuencia P I I P P P, donde P representa a un número par, e I representa a un número impar (cosa que puede probarse fácilmente). Así, pues, como por cada 6 términos, 2 son impares, y teniendo en cuenta que el único que se repite es el 1, nPentanacciImpares (6k) = 2k-1 para todo k > 0. Como los dos siguientes son impares, tenemos nPentanacciImpares (6k+1) = 2k, nPentanacciImpares (6k+2) = 2k+1, y lo mismo para los números de la forma 6k+3, 6k+4 y 6k+5. Se obtiene de este modo una solución muy eficiente: