{"id":8355,"date":"2023-12-09T06:00:49","date_gmt":"2023-12-09T04:00:49","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8355"},"modified":"2024-05-17T18:40:58","modified_gmt":"2024-05-17T16:40:58","slug":"09-dic-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/09-dic-23\/","title":{"rendered":"N\u00fameros de Pentanacci"},"content":{"rendered":"<p>Los n\u00fameros de Fibonacci se definen mediante las ecuaciones<\/p>\n<pre lang=\"text\">\n   F(0) = 0\n   F(1) = 1\n   F(n) = F(n-1) + F(n-2), si n > 1\n<\/pre>\n<p>Los primeros n\u00fameros de Fibonacci son<\/p>\n<pre lang=\"text\">\n   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...\n<\/pre>\n<p>Una generalizaci\u00f3n de los anteriores son los n\u00fameros de Pentanacci definidos por las siguientes ecuaciones<\/p>\n<pre lang=\"text\">\n   P(0) = 0\n   P(1) = 1\n   P(2) = 1\n   P(3) = 2\n   P(4) = 4\n   P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4\n<\/pre>\n<p>Los primeros n\u00fameros de Pentanacci son<\/p>\n<pre lang=\"text\">\n  0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...\n<\/pre>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   pentanacci  :: Integer -> Integer\n   pentanaccis :: [Integer]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>pentanacci n<\/code> es el <code>n<\/code>-\u00e9simo n\u00famero de Pentanacci. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> pentanacci 14\n     3525\n     \u03bb> pentanacci (10^5) `mod` 10^30\n     482929150584077921552549215816\n     \u03bb> length (show (pentanacci (10^5)))\n     29357\n<\/pre>\n<ul>\n<li><code>pentanaccis<\/code> es la lista de los n\u00fameros de Pentanacci. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> take 15 pentanacci\n     [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]\n<\/pre>\n<p><!--more--><\/p>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Numeros_de_Pentanacci where\n\nimport Data.List (genericIndex, zipWith5)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\nimport Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\npentanacci1  :: Integer -> Integer\npentanacci1  0 = 0\npentanacci1  1 = 1\npentanacci1  2 = 1\npentanacci1  3 = 2\npentanacci1  4 = 4\npentanacci1  n = sum [pentanacci1 (n-k) | k <- [1..5]]\n\npentanaccis1 :: [Integer]\npentanaccis1 = [pentanacci1 n | n <- [0..]]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\npentanaccis2 :: [Integer]\npentanaccis2 =\n  0 : 1 : 1 : 2 : 4 : zipWith5 f (r 0) (r 1) (r 2) (r 3) (r 4)\n  where f a b c d e = a+b+c+d+e\n        r n         = drop n pentanaccis2\n\npentanacci2  :: Integer -> Integer\npentanacci2 n = pentanaccis2 `genericIndex` n\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\npentanaccis3 :: [Integer]\npentanaccis3 = p (0, 1, 1, 2, 4)\n  where p (a, b, c, d, e) = a : p (b, c, d, e, a + b + c + d + e)\n\npentanacci3  :: Integer -> Integer\npentanacci3 n = pentanaccis3 `genericIndex` n\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\npentanaccis4 :: [Integer]\npentanaccis4 = 0: 1: 1: 2: 4: p pentanaccis4\n  where p (a:b:c:d:e:xs) = (a+b+c+d+e): p (b:c:d:e:xs)\n\npentanacci4  :: Integer -> Integer\npentanacci4 n = pentanaccis4 `genericIndex` n\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"ej1\" $\n    take 15 pentanaccis1 `shouldBe`\n    [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]\n  it \"ej2\" $\n    take 15 pentanaccis2 `shouldBe`\n    [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]\n  it \"ej3\" $\n    take 15 pentanaccis3 `shouldBe`\n    [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]\n  it \"ej4\" $\n    take 15 pentanaccis4 `shouldBe`\n    [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    4 examples, 0 failures\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_pentanaccis :: NonNegative Int -> Bool\nprop_pentanaccis (NonNegative n) =\n  all (== pentanaccis1 !! n)\n      [pentanaccis1 !! n,\n       pentanaccis2 !! n,\n       pentanaccis3 !! n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=25}) prop_pentanaccis\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> pentanacci1 25\n--    5976577\n--    (4.64 secs, 1,865,626,496 bytes)\n--    \u03bb> pentanacci2 25\n--    5976577\n--    (0.00 secs, 578,584 bytes)\n--\n--    \u03bb> length (show (pentanacci2 (10^5)))\n--    29357\n--    (1.16 secs, 2,543,272,136 bytes)\n--    \u03bb> length (show (pentanacci3 (10^5)))\n--    29357\n--    (1.00 secs, 2,560,881,608 bytes)\n--    \u03bb> length (show (pentanacci4 (10^5)))\n--    29357\n--    (1.03 secs, 2,592,078,744 bytes)\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom itertools import count, islice\nfrom sys import set_int_max_str_digits\nfrom timeit import Timer, default_timer\nfrom typing import Iterator\n\nset_int_max_str_digits(30000)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef pentanacci1(n: int) -> int:\n    if n == 0:\n        return 0\n    if n == 1:\n        return 1\n    if n == 2:\n        return 1\n    if n == 3:\n        return 2\n    if n == 4:\n        return 4\n    return sum((pentanacci1(n-k) for k in range(1, 6)))\n\ndef pentanaccis1() -> Iterator[int]:\n    return (pentanacci1(n) for n in count())\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef pentanaccis2() -> Iterator[int]:\n    seq = [0, 1, 1, 2, 4]\n    while True:\n        yield seq[0]\n        seq.append(sum(seq))\n        seq.pop(0)\n\ndef nth(i: Iterator[int], n: int) -> int:\n    return list(islice(i, n, n+1))[0]\n\ndef pentanacci2(n: int) -> int:\n    return nth(pentanaccis2(), n)\n\n# Verificaci\u00f3n\n# ============\n\ndef test_pentanacci() -> None:\n    assert pentanacci1(14) == 3525\n    assert list(islice(pentanaccis1(), 15)) == \\\n        [0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525]\n    assert pentanacci2(14) == 3525\n    assert list(islice(pentanaccis2(), 15)) == \\\n        [0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_pentanacci()\n#    Verificado\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\ndef test_pentanacci_equiv() -> bool:\n    return list(islice(pentanaccis1(), 25)) == list(islice(pentanaccis2(), 25))\n\n# La comprobaci\u00f3n es\n#    >>> test_pentanacci_equiv()\n#    True\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('pentanacci1(28)')\n#    8.24 segundos\n#    >>> tiempo('pentanacci2(28)')\n#    0.00 segundos\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Los n\u00fameros de Fibonacci se definen mediante las ecuaciones F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2), si n > 1 Los primeros n\u00fameros de Fibonacci son 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, &#8230; Una generalizaci\u00f3n de los anteriores son los n\u00fameros&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"default","_kad_post_title":"default","_kad_post_layout":"default","_kad_post_sidebar_id":"","_kad_post_content_style":"default","_kad_post_vertical_padding":"default","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[581],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8355"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=8355"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8355\/revisions"}],"predecessor-version":[{"id":8568,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8355\/revisions\/8568"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8355"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8355"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8355"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}