F(0) = 0
   F(1) = 1
   F(n) = F(n-1) + F(n-2), si n > 1

   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

   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

  0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...

   pentanacci  :: Integer -> Integer
   pentanaccis :: [Integer]

     λ> pentanacci 14
     3525
     λ> pentanacci (10^5) `mod` 10^30
     482929150584077921552549215816
     λ> length (show (pentanacci (10^5)))
     29357

     λ> take 15 pentanacci
     [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]

module Numeros_de_Pentanacci where

import Data.List (genericIndex, zipWith5)
import Test.Hspec (Spec, hspec, it, shouldBe)
import Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs)

-- 1ª solución
-- ===========

pentanacci1  :: Integer -> Integer
pentanacci1  0 = 0
pentanacci1  1 = 1
pentanacci1  2 = 1
pentanacci1  3 = 2
pentanacci1  4 = 4
pentanacci1  n = sum [pentanacci1 (n-k) | k <- [1..5]]

pentanaccis1 :: [Integer]
pentanaccis1 = [pentanacci1 n | n <- [0..]]

-- 2ª solución
-- ===========

pentanaccis2 :: [Integer]
pentanaccis2 =
  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 pentanaccis2

pentanacci2  :: Integer -> Integer
pentanacci2 n = pentanaccis2 `genericIndex` n

-- 3ª solución
-- ===========

pentanaccis3 :: [Integer]
pentanaccis3 = p (0, 1, 1, 2, 4)
  where p (a, b, c, d, e) = a : p (b, c, d, e, a + b + c + d + e)

pentanacci3  :: Integer -> Integer
pentanacci3 n = pentanaccis3 `genericIndex` n

-- 4ª solución
-- ===========

pentanaccis4 :: [Integer]
pentanaccis4 = 0: 1: 1: 2: 4: p pentanaccis4
  where p (a:b:c:d:e:xs) = (a+b+c+d+e): p (b:c:d:e:xs)

pentanacci4  :: Integer -> Integer
pentanacci4 n = pentanaccis4 `genericIndex` n

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "ej1" $
    take 15 pentanaccis1 `shouldBe`
    [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]
  it "ej2" $
    take 15 pentanaccis2 `shouldBe`
    [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]
  it "ej3" $
    take 15 pentanaccis3 `shouldBe`
    [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]
  it "ej4" $
    take 15 pentanaccis4 `shouldBe`
    [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]

-- La verificación es
--    λ> verifica
--
--    4 examples, 0 failures

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_pentanaccis :: NonNegative Int -> Bool
prop_pentanaccis (NonNegative n) =
  all (== pentanaccis1 !! n)
      [pentanaccis1 !! n,
       pentanaccis2 !! n,
       pentanaccis3 !! n]

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=25}) prop_pentanaccis
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> pentanacci1 25
--    5976577
--    (4.64 secs, 1,865,626,496 bytes)
--    λ> pentanacci2 25
--    5976577
--    (0.00 secs, 578,584 bytes)
--
--    λ> length (show (pentanacci2 (10^5)))
--    29357
--    (1.16 secs, 2,543,272,136 bytes)
--    λ> length (show (pentanacci3 (10^5)))
--    29357
--    (1.00 secs, 2,560,881,608 bytes)
--    λ> length (show (pentanacci4 (10^5)))
--    29357
--    (1.03 secs, 2,592,078,744 bytes)

from itertools import count, islice
from sys import set_int_max_str_digits
from timeit import Timer, default_timer
from typing import Iterator

set_int_max_str_digits(30000)

# 1ª solución
# ===========

def pentanacci1(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 1
    if n == 3:
        return 2
    if n == 4:
        return 4
    return sum((pentanacci1(n-k) for k in range(1, 6)))

def pentanaccis1() -> Iterator[int]:
    return (pentanacci1(n) for n in count())

# 2ª solución
# ===========

def pentanaccis2() -> Iterator[int]:
    seq = [0, 1, 1, 2, 4]
    while True:
        yield seq[0]
        seq.append(sum(seq))
        seq.pop(0)

def nth(i: Iterator[int], n: int) -> int:
    return list(islice(i, n, n+1))[0]

def pentanacci2(n: int) -> int:
    return nth(pentanaccis2(), n)

# Verificación
# ============

def test_pentanacci() -> None:
    assert pentanacci1(14) == 3525
    assert list(islice(pentanaccis1(), 15)) == \
        [0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525]
    assert pentanacci2(14) == 3525
    assert list(islice(pentanaccis2(), 15)) == \
        [0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525]
    print("Verificado")

# La verificación es
#    >>> test_pentanacci()
#    Verificado

# Comprobación de equivalencia
# ============================

# La propiedad es
def test_pentanacci_equiv() -> bool:
    return list(islice(pentanaccis1(), 25)) == list(islice(pentanaccis2(), 25))

# La comprobación es
#    >>> test_pentanacci_equiv()
#    True

# Comparación de eficiencia
# =========================

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('pentanacci1(28)')
#    8.24 segundos
#    >>> tiempo('pentanacci2(28)')
#    0.00 segundos