Los n\u00fameros triangulares se forman como sigue<\/p>\n
\n * * *\n * * * *\n * * *\n 1 3 6\n<\/pre>\nLa sucesi\u00f3n de los n\u00fameros triangulares se obtiene sumando los n\u00fameros naturales. As\u00ed, los 5 primeros n\u00fameros triangulares son<\/p>\n
\n 1 = 1\n 3 = 1 + 2\n 6 = 1 + 2 + 3\n 10 = 1 + 2 + 3 + 4\n 15 = 1 + 2 + 3 + 4 + 5\n<\/pre>\nDefinir la funci\u00f3n<\/p>\n
\n descomposicionesTriangulares :: Int -> [(Int, Int, Int)]\n<\/pre>\ntal que descomposicionesTriangulares n<\/code> es la lista de las ternas correspondientes a las descomposiciones de n<\/code> en tres sumandos, como m\u00e1ximo, formados por n\u00fameros triangulares. Por ejemplo,<\/p>\n\n \u03bb> descomposicionesTriangulares 4\n []\n \u03bb> descomposicionesTriangulares 5\n [(1,1,3)]\n \u03bb> descomposicionesTriangulares 12\n [(1,1,10),(3,3,6)]\n \u03bb> descomposicionesTriangulares 30\n [(1,1,28),(3,6,21),(10,10,10)]\n \u03bb> descomposicionesTriangulares 61\n [(1,15,45),(3,3,55),(6,10,45),(10,15,36)]\n \u03bb> descomposicionesTriangulares 52\n [(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)]\n \u03bb> descomposicionesTriangulares 82\n [(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)]\n \u03bb> length (descomposicionesTriangulares (5*10^5))\n 124\n<\/pre>\n<\/p>\n
1. Soluciones en Haskell<\/h2>\n\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ndescomposicionesTriangulares1 :: Int -> [(Int, Int, Int)]\ndescomposicionesTriangulares1 n =\n [(x,y,z) | x <- xs,\n y <- xs,\n z <- xs,\n x <= y && y <= z,\n x + y + z == n]\n where xs = takeWhile (<=n) triangulares\n\n-- triangulares es la lista de los n\u00fameros triangulares. Por ejemplo,\n-- take 9 triangulares == [1,3,6,10,15,21,28,36,45]\ntriangulares :: [Int]\ntriangulares = scanl (+) 1 [2..]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ndescomposicionesTriangulares2 :: Int -> [(Int, Int, Int)]\ndescomposicionesTriangulares2 n =\n [(x,y,z) | x <- xs,\n y <- xs,\n x <= y,\n z <- xs,\n y <= z,\n x + y + z == n]\n where xs = takeWhile (<=n) triangulares\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ndescomposicionesTriangulares3 :: Int -> [(Int, Int, Int)]\ndescomposicionesTriangulares3 n =\n [(x,y,z) | x <- xs,\n y <- xs,\n x <= y,\n let z = n - x - y,\n y <= z,\n z `elem` xs]\n where xs = takeWhile (<=n) triangulares\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\ndescomposicionesTriangulares4 :: Int -> [(Int, Int, Int)]\ndescomposicionesTriangulares4 n =\n [(x,y,n-x-y) | x <- xs,\n y <- dropWhile ( [(Int, Int, Int)]) -> Spec\nspecG descomposicionesTriangulares = do\n it \"e1\" $\n descomposicionesTriangulares 4 `shouldBe`\n []\n it \"e2\" $\n descomposicionesTriangulares 5 `shouldBe`\n [(1,1,3)]\n it \"e3\" $\n descomposicionesTriangulares 12 `shouldBe`\n [(1,1,10),(3,3,6)]\n it \"e4\" $\n descomposicionesTriangulares 30 `shouldBe`\n [(1,1,28),(3,6,21),(10,10,10)]\n it \"e5\" $\n descomposicionesTriangulares 61 `shouldBe`\n [(1,15,45),(3,3,55),(6,10,45),(10,15,36)]\n it \"e6\" $\n descomposicionesTriangulares 52 `shouldBe`\n [(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)]\n it \"e7\" $\n descomposicionesTriangulares 82 `shouldBe`\n [(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)]\n\nspec :: Spec\nspec = do\n describe \"def. 1\" $ specG descomposicionesTriangulares1\n describe \"def. 2\" $ specG descomposicionesTriangulares2\n describe \"def. 3\" $ specG descomposicionesTriangulares3\n describe \"def. 4\" $ specG descomposicionesTriangulares4\n\n-- La verificaci\u00f3n es\n-- \u03bb> verifica\n-- 28 examples, 0 failures\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_descomposicionesTriangulares_equiv :: Positive Int -> Bool\nprop_descomposicionesTriangulares_equiv (Positive n) =\n all (== descomposicionesTriangulares1 n)\n [descomposicionesTriangulares2 n,\n descomposicionesTriangulares3 n,\n descomposicionesTriangulares4 n]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_descomposicionesTriangulares_equiv\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> last (descomposicionesTriangulares1 (2*10^4))\n-- (5671,6328,8001)\n-- (3.34 secs, 1,469,517,168 bytes)\n-- \u03bb> last (descomposicionesTriangulares2 (2*10^4))\n-- (5671,6328,8001)\n-- (1.29 secs, 461,433,928 bytes)\n-- \u03bb> last (descomposicionesTriangulares3 (2*10^4))\n-- (5671,6328,8001)\n-- (0.08 secs, 6,574,056 bytes)\n--\n-- \u03bb> last (descomposicionesTriangulares3 (5*10^5))\n-- (140185,148240,211575)\n-- (2.12 secs, 151,137,280 bytes)\n-- \u03bb> last (descomposicionesTriangulares4 (5*10^5))\n-- (140185,148240,211575)\n-- (2.30 secs, 103,280,216 bytes)\n<\/pre>\n2. Soluciones en Python<\/h2>\n\nfrom itertools import count, dropwhile, takewhile\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\nfrom typing import Iterator\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# triangular(n) es el n-\u00e9simo n\u00famero triangular. Por ejemplo,\n# triangular(9) == 45\ndef triangular(n: int) -> int:\n if n == 1:\n return 1\n return triangular(n-1) + n\n\n# triangulares1() es la lista de los n\u00fameros triangulares. Por ejemplo,\n# >>> from itertools import islice\n# >>> list(islice(triangulares1(), 10))\n# [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]\ndef triangulares1() -> Iterator[int]:\n return (triangular(n) for n in count(1))\n\ndef descomposicionesTriangulares1(n: int) -> list[tuple[int, int, int]]:\n xs = list(takewhile(lambda x : x <= n, triangulares1()))\n return [(x,y,z) for x in xs for y in xs for z in xs if\n x <= y <= z and x + y + z == n]\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef triangulares2() -> Iterator[int]:\n return ((n*(n+1)) \/\/ 2 for n in count(1))\n\ndef descomposicionesTriangulares2(n: int) -> list[tuple[int, int, int]]:\n xs = list(takewhile(lambda x : x <= n, triangulares2()))\n return [(x,y,z) for x in xs for y in xs for z in xs if\n x <= y <= z and x + y + z == n]\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef descomposicionesTriangulares3(n: int) -> list[tuple[int, int, int]]:\n xs = list(takewhile(lambda x : x <= n, triangulares2()))\n return [(x,y,z)\n for x in xs\n for y in xs\n if x <= y\n for z in xs\n if y <= z\n if x + y + z == n]\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef descomposicionesTriangulares4(n: int) -> list[tuple[int, int, int]]:\n xs = list(takewhile(lambda x : x <= n, triangulares2()))\n ts = []\n for x in xs:\n for y in xs:\n if x <= y:\n z = n - x - y\n if y <= z and z in xs:\n ts.append((x, y, z))\n return ts\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\ndef descomposicionesTriangulares5(n: int) -> list[tuple[int, int, int]]:\n xs = list(takewhile(lambda a : a <= n, triangulares2()))\n ts = []\n for x in xs:\n ys = list(dropwhile(lambda y: y < x, xs))\n for y in ys:\n z = n - x - y\n if y <= z and z in xs:\n ts.append((x, y, z))\n return ts\n\n# Verificaci\u00f3n\n# ============\n\ndef test_descomposicionesTriangulares() -> None:\n for descomposicionesTriangulares in [descomposicionesTriangulares1,\n descomposicionesTriangulares2,\n descomposicionesTriangulares3,\n descomposicionesTriangulares4,\n descomposicionesTriangulares5]:\n assert descomposicionesTriangulares(4) ==\\\n []\n assert descomposicionesTriangulares(5) ==\\\n [(1,1,3)]\n assert descomposicionesTriangulares(12) ==\\\n [(1,1,10),(3,3,6)]\n assert descomposicionesTriangulares(30) ==\\\n [(1,1,28),(3,6,21),(10,10,10)]\n assert descomposicionesTriangulares(61) ==\\\n [(1,15,45),(3,3,55),(6,10,45),(10,15,36)]\n assert descomposicionesTriangulares(52) ==\\\n [(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)]\n assert descomposicionesTriangulares(82) ==\\\n [(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)]\n print(\"Verificado\")\n\n# La verificaci\u00f3n es\n# >>> test_descomposicionesTriangulares()\n# Verificado\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=1000))\ndef test_descomposicionesTriangulares_equiv(n: int) -> None:\n r = descomposicionesTriangulares1(n)\n assert descomposicionesTriangulares2(n) == r\n assert descomposicionesTriangulares3(n) == r\n assert descomposicionesTriangulares4(n) == r\n\n# La comprobaci\u00f3n es\n# >>> test_descomposicionesTriangulares_equiv()\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('descomposicionesTriangulares1(6*10**4)[-1]')\n# 2.16 segundos\n# >>> tiempo('descomposicionesTriangulares2(6*10**4)[-1]')\n# 2.05 segundos\n# >>> tiempo('descomposicionesTriangulares3(6*10**4)[-1]')\n# 1.04 segundos\n# >>> tiempo('descomposicionesTriangulares4(6*10**4)[-1]')\n# 0.10 segundos\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Los n\u00fameros triangulares se forman como sigue * * * * * * * * * * 1 3 6 La sucesi\u00f3n de los n\u00fameros triangulares se obtiene sumando los n\u00fameros naturales. As\u00ed, los 5 primeros n\u00fameros triangulares son 1 = 1 3 = 1 + 2 6 = 1 + 2 + 3 10…<\/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\/8586"}],"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=8586"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8586\/revisions"}],"predecessor-version":[{"id":8591,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8586\/revisions\/8591"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8586"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8586"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8586"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}