{"id":8367,"date":"2024-01-04T06:00:07","date_gmt":"2024-01-04T04:00:07","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8367"},"modified":"2024-02-02T17:07:39","modified_gmt":"2024-02-02T15:07:39","slug":"04-ene-24","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/04-ene-24\/","title":{"rendered":"Representaciones de un n\u00famero como suma de dos cuadrados"},"content":{"rendered":"

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

\n   representaciones :: Integer -> [(Integer,Integer)]\n<\/pre>\n
tal que representaciones n<\/code> es la lista de pares de n\u00fameros naturales (x,y) tales que n = x\u00b2 + y\u00b2. Por ejemplo.<\/p>\n
\n   representaciones  20              ==  [(2,4)]\n   representaciones  25              ==  [(0,5),(3,4)]\n   representaciones 325              ==  [(1,18),(6,17),(10,15)]\n   length (representaciones (10^14)) == 8\n<\/pre>\n
Comprobar con QuickCheck que un n\u00famero natural n se puede representar como suma de dos cuadrados si, y s\u00f3lo si, en la factorizaci\u00f3n prima de n todos los exponentes de sus factores primos congruentes con 3 m\u00f3dulo 4 son pares.
\n<\/p>\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
\nmodule Representaciones_de_un_numero_como_suma_de_dos_cuadrados where\n\nimport Data.List (genericLength, group)\nimport Data.Numbers.Primes (primeFactors)\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nrepresentaciones1 :: Integer -> [(Integer,Integer)]\nrepresentaciones1 n =\n  [(x,y) | x <- [0..n], y <- [x..n], n == x*x + y*y]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nrepresentaciones2 :: Integer -> [(Integer,Integer)]\nrepresentaciones2 n =\n  [(x,raiz z) | x <- [0..raiz (n `div` 2)],\n                let z = n - x*x,\n                esCuadrado z]\n\n-- (raiz x) es la ra\u00edz cuadrada entera de x. Por ejemplo,\n--    raiz 25  ==  5\n--    raiz 24  ==  4\n--    raiz 26  ==  5\nraiz :: Integer -> Integer\nraiz 0 = 0\nraiz 1 = 1\nraiz x = aux (0,x)\n    where aux (a,b) | d == x    = c\n                    | c == a    = a\n                    | d < x     = aux (c,b)\n                    | otherwise = aux (a,c)\n              where c = (a+b) `div` 2\n                    d = c^2\n\n-- Nota: La siguiente definici\u00f3n de ra\u00edz cuadrada falla para n\u00fameros\n-- grandes.\n--    raiz' :: Integer -> Integer\n--    raiz' = floor . sqrt . fromIntegral\n-- Por ejemplo,\n--    \u03bb> raiz' (10^50)\n--    9999999999999998758486016\n--    \u03bb> raiz (10^50)\n--    10000000000000000000000000\n\n-- (esCuadrado x) se verifica si x es un n\u00famero al cuadrado. Por\n-- ejemplo,\n--    esCuadrado 25  ==  True\n--    esCuadrado 26  ==  False\nesCuadrado :: Integer -> Bool\nesCuadrado x = x == y * y\n  where y = raiz x\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nrepresentaciones3 :: Integer -> [(Integer, Integer)]\nrepresentaciones3 n = aux 0 (raiz n)\n  where aux x y\n          | x > y     = []\n          | otherwise = case compare (x*x + y*y) n of\n                          LT -> aux (x + 1) y\n                          EQ -> (x, y) : aux (x + 1) (y - 1)\n                          GT -> aux x (y - 1)\n\n-- Verificaci\u00f3n                                                     --\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: (Integer -> [(Integer, Integer)]) -> Spec\nspecG representaciones = do\n  it \"e1\" $\n    representaciones  20 `shouldBe` [(2,4)]\n  it \"e2\" $\n    representaciones  25 `shouldBe` [(0,5),(3,4)]\n  it \"e3\" $\n    representaciones 325 `shouldBe` [(1,18),(6,17),(10,15)]\n\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG representaciones1\n  describe \"def. 2\" $ specG representaciones2\n  describe \"def. 3\" $ specG representaciones3\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    9 examples, 0 failures\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_representaciones :: Positive Integer -> Bool\nprop_representaciones (Positive n) =\n  all (== representaciones1 n)\n      [representaciones2 n,\n       representaciones3 n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_representaciones\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> representaciones1 4000\n--    [(20,60),(36,52)]\n--    (4.95 secs, 2,434,929,624 bytes)\n--    \u03bb> representaciones2 4000\n--    [(20,60),(36,52)]\n--    (0.00 secs, 599,800 bytes)\n--    \u03bb> representaciones3 4000\n--    [(20,60),(36,52)]\n--    (0.01 secs, 591,184 bytes)\n--\n--    \u03bb> length (representaciones2 (10^14))\n--    8\n--    (6.64 secs, 5,600,837,088 bytes)\n--    \u03bb> length (representaciones3 (10^14))\n--    8\n--    (9.37 secs, 4,720,548,264 bytes)\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_representacion :: Positive Integer -> Bool\nprop_representacion (Positive n) =\n  not (null (representaciones2 n)) ==\n  all (\\(p,e) -> p `mod` 4 \/= 3 || even e) (factorizacion n)\n\n-- (factorizacion n) es la factorizaci\u00f3n prima de n. Por ejemplo,\n--    factorizacion 600  ==  [(2,3),(3,1),(5,2)]\nfactorizacion :: Integer -> [(Integer,Integer)]\nfactorizacion n =\n  map (\\xs -> (head xs, genericLength xs)) (group (primeFactors n))\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_representacion\n--    +++ OK, passed 100 tests.\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom math import floor, sqrt\nfrom timeit import Timer, default_timer\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\nfrom sympy import factorint\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef representaciones1(n: int) -> list[tuple[int, int]]:\n    return [(x,y) for x in range(n+1) for y in range(x,n+1) if n == x*x + y*y]\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# raiz(x) es la ra\u00edz cuadrada entera de x. Por ejemplo,\n#    raiz(25)     ==  5\n#    raiz(24)     ==  4\n#    raiz(26)     ==  5\n#    raiz(10**46) == 100000000000000000000000\ndef raiz(x: int) -> int:\n    def aux(a: int, b: int) -> int:\n        c = (a+b) \/\/ 2\n        d = c**2\n        if d == x:\n            return c\n        if c == a:\n            return a\n        if d < x:\n            return aux (c,b)\n        return aux (a,c)\n    if x == 0:\n        return 0\n    if x == 1:\n        return 1\n    return aux(0, x)\n\n# Nota. La siguiente definici\u00f3n de ra\u00edz cuadrada entera falla para\n# n\u00fameros grandes. Por ejemplo,\n#    >>> raiz2(10**46)\n#    99999999999999991611392\ndef raiz2(x: int) -> int:\n    return floor(sqrt(x))\n\n# esCuadrado(x) se verifica si x es un n\u00famero al cuadrado. Por\n# ejemplo,\n#    esCuadrado(25)     == True\n#    esCuadrado(26)     == False\n#    esCuadrado(10**46) == True\n#    esCuadrado(10**47) == False\ndef esCuadrado(x: int) -> bool:\n    y = raiz(x)\n    return x == y * y\n\ndef representaciones2(n: int) -> list[tuple[int, int]]:\n    r: list[tuple[int, int]] = []\n    for x in range(1 + raiz(n \/\/ 2)):\n        z = n - x*x\n        if esCuadrado(z):\n            r.append((x, raiz(z)))\n    return r\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef representaciones3(n: int) -> list[tuple[int, int]]:\n    r: list[tuple[int, int]] = []\n    for x in range(1 + raiz(n \/\/ 2)):\n        y = n - x*x\n        z = raiz(y)\n        if y == z * z:\n            r.append((x, z))\n    return r\n\n# Verificaci\u00f3n\n# ============\n\ndef test_representaciones() -> None:\n    assert representaciones1(20) == [(2,4)]\n    assert representaciones1(25) == [(0,5),(3,4)]\n    assert representaciones1(325) == [(1,18),(6,17),(10,15)]\n    assert representaciones2(20) == [(2,4)]\n    assert representaciones2(25) == [(0,5),(3,4)]\n    assert representaciones2(325) == [(1,18),(6,17),(10,15)]\n    assert representaciones3(20) == [(2,4)]\n    assert representaciones3(25) == [(0,5),(3,4)]\n    assert representaciones3(325) == [(1,18),(6,17),(10,15)]\n    print(\"Verificado\")\n\n# La comprobaci\u00f3n es\n#    >>> test_representaciones()\n#    Verificado\n\n# Equivalencia de las definiciones de representaciones\n# ====================================================\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=1000))\ndef test_representaciones_equiv(x: int) -> None:\n    xs = representaciones1(x)\n    assert representaciones2(x) == xs\n    assert representaciones3(x) == xs\n\n# La comprobaci\u00f3n es\n#    >>> test_representaciones_equiv()\n#    >>>\n\n# Comparaci\u00f3n de eficiencia de las definiciones de representaciones\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('representaciones1(5000)')\n#    1.27 segundos\n#    >>> tiempo('representaciones2(5000)')\n#    0.00 segundos\n#    >>> tiempo('representaciones3(5000)')\n#    0.00 segundos\n#\n#    >>> tiempo('len(representaciones2(10**12))')\n#    11.54 segundos\n#    >>> tiempo('len(representaciones3(10**12))')\n#    12.08 segundos\n\n# Comprobaci\u00f3n de la propiedad\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=1000))\ndef test_representaciones_prop(n: int) -> None:\n    factores = factorint(n)\n    assert (len(representaciones2(n)) > 0) == \\\n        all(p % 4 != 3 or e % 2 == 0 for p, e in factores.items())\n\n# La comprobaci\u00f3n es\n#    >>> test_representaciones_prop()\n#    >>>\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Definir la funci\u00f3n representaciones :: Integer -> [(Integer,Integer)] tal que representaciones n es la lista de pares de n\u00fameros naturales (x,y) tales que n = x\u00b2 + y\u00b2. Por ejemplo. representaciones 20 == [(2,4)] representaciones 25 == [(0,5),(3,4)] representaciones 325 == [(1,18),(6,17),(10,15)] length (representaciones (10^14)) == 8 Comprobar con QuickCheck que un n\u00famero natural n…<\/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\/8367"}],"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=8367"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8367\/revisions"}],"predecessor-version":[{"id":8405,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8367\/revisions\/8405"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8367"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8367"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8367"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}