Menu Close

Cantidad de números Pentanacci impares

José A. Alonso,

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 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

   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
Medio
, , , , , , , ,

3 soluciones de “Cantidad de números Pentanacci impares”

  1. Responder
    josejuan 
    nPentanacciImpares :: ℤ → ℤ
nPentanacciImpares 0 = 0
nPentanacciImpares 1 = 1
nPentanacciImpares 2 = 1
nPentanacciImpares n = 2 * d - 1 + case r of { 0 → 0; 1 → 1; _ → 2 }
                       where (d, r) = n `divMod` 6
  2. Responder
    abrdelrod

    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:

    nPentanacciImpares :: Integer -> Integer
nPentanacciImpares 0 = 0
nPentanacciImpares 1 = 1
nPentanacciImpares 2 = 1
nPentanacciImpares n | m == 0    = div n 3 - 1
                     | m == 1    = div n 3 
                     | m == 2    = div n 3 + 1
                     | m == 3    = f (n+3)
                     | m == 4    = f (n+2) 
                     | otherwise = f (n+1)
                     where m = rem n 6
                           f = nPentanacciImpares
  3. Responder
    erisan 
    import Data.List
 
nPentanacciImpares :: Integer -> Integer
nPentanacciImpares n = genericLength (filter odd (drop 2 (genericTake (n + 1) pentanacci)))
 
pentanacci :: [Integer]
pentanacci = 0:1:1:2:4: map (sum . take 5) (tails pentanacci)

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.