{"id":7447,"date":"2022-10-18T06:00:15","date_gmt":"2022-10-18T04:00:15","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7447"},"modified":"2022-12-14T12:30:30","modified_gmt":"2022-12-14T10:30:30","slug":"ternas-pitagoricas-con-suma-dada","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/ternas-pitagoricas-con-suma-dada\/","title":{"rendered":"Ternas pitag\u00f3ricas con suma dada"},"content":{"rendered":"

Una terna pitag\u00f3rica es una terna de n\u00fameros naturales (a,b,c) tal que a<b<c y a\u00b2+b\u00b2=c\u00b2. Por ejemplo (3,4,5) es una terna pitag\u00f3rica.<\/p>\n

Definir la funci\u00f3n<\/p>\n

\n   ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)]\n<\/pre>\n
tal que ternasPitagoricas x<\/code> es la lista de las ternas pitag\u00f3ricas cuya suma es x<\/code>. Por ejemplo,<\/p>\n
\n   ternasPitagoricas 12     == [(3,4,5)]\n   ternasPitagoricas 60     == [(10,24,26),(15,20,25)]\n   ternasPitagoricas (10^6) == [(218750,360000,421250),(200000,375000,425000)]\n<\/pre>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\nimport Data.List (nub,sort)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n                                                   --\n-- ===========\n\nternasPitagoricas1 :: Integer -> [(Integer,Integer,Integer)]\nternasPitagoricas1 x =\n  [(a,b,c) | a <- [0..x],\n             b <- [a+1..x],\n             c <- [b+1..x],\n             a^2 + b^2 == c^2,\n             a+b+c == x]\n\n-- 2\u00aa soluci\u00f3n                                                   --\n-- ===========\n\nternasPitagoricas2 :: Integer -> [(Integer,Integer,Integer)]\nternasPitagoricas2 x =\n  [(a,b,c) | a <- [1..x],\n             b <- [a+1..x-a],\n             let c = x-a-b,\n             a^2+b^2 == c^2]\n\n-- 3\u00aa soluci\u00f3n                                                   --\n-- ===========\n\n-- Todas las ternas pitag\u00f3ricas primitivas (a,b,c) pueden representarse\n-- por\n--    a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2,\n-- con 1 <= n < m. (Ver en https:\/\/bit.ly\/35UNY6L ).\n\nternasPitagoricas3 :: Integer -> [(Integer,Integer,Integer)]\nternasPitagoricas3 x =\n  nub [(d*a,d*b,d*c) | d <- [1..x],\n                       x `mod` d == 0,\n                       (a,b,c) <- aux (x `div` d)]\n  where\n    aux y = [(a,b,c) | m <- [2..limite],\n                       n <- [1..m-1],\n                       let [a,b] = sort [m^2 - n^2, 2*m*n],\n                       let c = m^2 + n^2,\n                       a+b+c == y]\n      where limite = ceiling (sqrt (fromIntegral y))\n\n-- Equivalencia de las definiciones\n-- ================================\n\n-- La propiedad es\nprop_ternasPitagoricas :: Positive Integer -> Bool\nprop_ternasPitagoricas (Positive x) =\n  all (== (ternasPitagoricas1 x))\n      [ternasPitagoricas2 x,\n       ternasPitagoricas3 x]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_ternasPitagoricas\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> ternasPitagoricas1 200\n--    [(40,75,85)]\n--    (1.90 secs, 2,404,800,856 bytes)\n--    \u03bb> ternasPitagoricas2 200\n--    [(40,75,85)]\n--    (0.06 secs, 19,334,232 bytes)\n--    \u03bb> ternasPitagoricas3 200\n--    [(40,75,85)]\n--    (0.01 secs, 994,224 bytes)\n--\n--    \u03bb> ternasPitagoricas2 3000\n--    [(500,1200,1300),(600,1125,1275),(750,1000,1250)]\n--    (4.41 secs, 4,354,148,136 bytes)\n--    \u03bb> ternasPitagoricas3 3000\n--    [(500,1200,1300),(600,1125,1275),(750,1000,1250)]\n--    (0.05 secs, 17,110,360 bytes)\n<\/pre>\n
El c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom math import ceil, sqrt\nfrom timeit import Timer, default_timer\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\n# 1\u00aa soluci\u00f3n                                                   --\n# ===========\n\ndef ternasPitagoricas1(x: int) -> list[tuple[int, int, int]]:\n    return [(a, b, c)\n            for a in range(0, x+1)\n            for b in range(a+1, x+1)\n            for c in range(b+1, x+1)\n            if a**2 + b**2 == c**2 and a + b + c == x]\n\n# 2\u00aa soluci\u00f3n                                                   --\n# ===========\n\ndef ternasPitagoricas2(x: int) -> list[tuple[int, int, int]]:\n    return [(a, b, c)\n            for a in range(1, x+1)\n            for b in range(a+1, x-a+1)\n            for c in [x - a - b]\n            if a**2 + b**2 == c**2]\n\n# 3\u00aa soluci\u00f3n                                                   --\n# ===========\n\n# Todas las ternas pitag\u00f3ricas primitivas (a,b,c) pueden representarse\n# por\n#    a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2,\n# con 1 <= n < m. (Ver en https:\/\/bit.ly\/35UNY6L ).\n\ndef ternasPitagoricas3(x: int) -> list[tuple[int, int, int]]:\n    def aux(y: int) -> list[tuple[int, int, int]]:\n        return [(a, b, c)\n                for m in range(2, 1 + ceil(sqrt(y)))\n                for n in range(1, m)\n                for a in [min(m**2 - n**2, 2*m*n)]\n                for b in [max(m**2 - n**2, 2*m*n)]\n                for c in [m**2 + n**2]\n                if a+b+c == y]\n\n    return list(set(((d*a, d*b, d*c)\n                     for d in range(1, x+1)\n                     for (a, b, c) in aux(x \/\/ d)\n                     if x % d == 0)))\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=50))\ndef test_ternasPitagoricas(n: int) -> None:\n    r = set(ternasPitagoricas1(n))\n    assert set(ternasPitagoricas2(n)) == r\n    assert set(ternasPitagoricas3(n)) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q ternas_pitagoricas_con_suma_dada.py\n#    1 passed in 0.35s\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('ternasPitagoricas1(300)')\n#    2.83 segundos\n#    >>> tiempo('ternasPitagoricas2(300)')\n#    0.01 segundos\n#    >>> tiempo('ternasPitagoricas3(300)')\n#    0.00 segundos\n#\n#    >>> tiempo('ternasPitagoricas2(3000)')\n#    1.48 segundos\n#    >>> tiempo('ternasPitagoricas3(3000)')\n#    0.02 segundos\n<\/pre>\n
El c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
Una terna pitag\u00f3rica es una terna de n\u00fameros naturales (a,b,c) tal que a<b<c y a\u00b2+b\u00b2=c\u00b2. Por ejemplo (3,4,5) es una terna pitag\u00f3rica. Definir la funci\u00f3n ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)] tal que ternasPitagoricas x es la lista de las ternas pitag\u00f3ricas cuya suma es x. Por ejemplo, ternasPitagoricas 12 == [(3,4,5)] ternasPitagoricas 60 == [(10,24,26),(15,20,25)]…<\/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":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_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\/7447"}],"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=7447"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7447\/revisions"}],"predecessor-version":[{"id":7668,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7447\/revisions\/7668"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7447"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7447"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7447"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}