Cantidad de números Pentanacci impares
Los números de Pentanacci se definen mediante las ecuaciones
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
0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...
Se observa 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
nPentanacciImpares :: Integer -> Integer
tal que (nPentanacciImpares n) es la cantidad de números impares distintos desde P(0) hasta P(n). Por ejemplo,
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
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