{"id":8358,"date":"2023-12-14T06:00:13","date_gmt":"2023-12-14T04:00:13","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8358"},"modified":"2024-02-02T17:09:10","modified_gmt":"2024-02-02T15:09:10","slug":"14-dic-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/14-dic-23\/","title":{"rendered":"El teorema de Navidad de Fermat"},"content":{"rendered":"<p>El 25 de diciembre de 1640, en una carta a Mersenne, Fermat demostr\u00f3 la conjetura de Girard: todo primo de la forma 4n+1 puede expresarse de manera \u00fanica como suma de dos cuadrados. Por eso es conocido como el <a href=\"http:\/\/bit.ly\/2Roso1o\">teorema de Navidad de Fermat<\/a>.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   representaciones :: Integer -> [(Integer,Integer)]\n   primosImparesConRepresentacionUnica :: [Integer]\n   primos4nM1 :: [Integer]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>representaciones n<\/code> es la lista de pares de n\u00fameros naturales <code>(x,y)<\/code> tales que <code>n = x^2 + y^2<\/code> con <code>x &lt;= y<\/code>. Por ejemplo.<\/li>\n<\/ul>\n<pre lang=\"text\">\n     representaciones  20           ==  [(2,4)]\n     representaciones  25           ==  [(0,5),(3,4)]\n     representaciones 325           ==  [(1,18),(6,17),(10,15)]\n     representaciones 100000147984  ==  [(0,316228)]\n     length (representaciones (10^10))    ==  6\n     length (representaciones (4*10^12))  ==  7\n<\/pre>\n<ul>\n<li><code>primosImparesConRepresentacionUnica<\/code> es la lista de los n\u00fameros primos impares que se pueden escribir exactamente de una manera como suma de cuadrados de pares de n\u00fameros naturales <code>(x,y)<\/code> con <code>x &lt;= y<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> take 20 primosImparesConRepresentacionUnica\n     [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]\n<\/pre>\n<ul>\n<li><code>primos4nM1<\/code> es la lista de los n\u00fameros primos que se pueden escribir como uno m\u00e1s un m\u00faltiplo de 4 (es decir, que son congruentes con 1 m\u00f3dulo 4). Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> take 20 primos4nM1\n     [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]\n<\/pre>\n<p>El teorema de Navidad de Fermat afirma que un n\u00famero primo impar p se puede escribir exactamente de una manera como suma de dos cuadrados de n\u00fameros naturales p = x\u00b2 + y\u00b2 (con x &lt;= y) si, y s\u00f3lo si, p se puede escribir como uno m\u00e1s un m\u00faltiplo de 4 (es decir, que es congruente con 1 m\u00f3dulo 4).<\/p>\n<p>Comprobar con QuickCheck el teorema de Navidad de Fermat; es decir, que para todo n\u00famero n, los n-\u00e9simos elementos de<br \/>\nprimosImparesConRepresentacionUnica y de primos4nM1 son iguales.<br \/>\n<!--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 El_teorema_de_Navidad_de_Fermat where\n\nimport Data.Numbers.Primes (primes)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n de representaciones\n-- =================================\n\nrepresentaciones :: Integer -> [(Integer,Integer)]\nrepresentaciones n =\n  [(x,y) | x <- [0..n], y <- [x..n], n == x*x + y*y]\n\n-- 2\u00aa definici\u00f3n de representaciones\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-- (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-- (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-- 3\u00aa definici\u00f3n de representaciones\n-- =================================\n\nrepresentaciones3 :: Integer -> [(Integer,Integer)]\nrepresentaciones3 n =\n  [(x,raiz3 z) | x <- [0..raiz3 (n `div` 2)]\n               , let z = n - x*x\n               , esCuadrado3 z]\n\n-- (esCuadrado3 x) se verifica si x es un n\u00famero al cuadrado. Por\n-- ejemplo,\n--    esCuadrado3 25  ==  True\n--    esCuadrado3 26  ==  False\nesCuadrado3 :: Integer -> Bool\nesCuadrado3 x = x == y * y\n  where y = raiz3 x\n\n-- (raiz3 x) es la ra\u00edz cuadrada entera de x. Por ejemplo,\n--    raiz3 25  ==  5\n--    raiz3 24  ==  4\n--    raiz3 26  ==  5\nraiz3 :: Integer -> Integer\nraiz3 x = floor (sqrt (fromIntegral x))\n\n-- 4\u00aa definici\u00f3n de representaciones\n-- =================================\n\nrepresentaciones4 :: Integer -> [(Integer, Integer)]\nrepresentaciones4 n = aux 0 (floor (sqrt (fromIntegral 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-- Equivalencia de las definiciones de representaciones\n-- ====================================================\n\n-- La propiedad es\nprop_representaciones_equiv :: Positive Integer -> Bool\nprop_representaciones_equiv (Positive n) =\n  representaciones  n == representaciones2 n &&\n  representaciones2 n == representaciones3 n &&\n  representaciones3 n == representaciones4 n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_representaciones_equiv\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia de las definiciones de representaciones\n-- =================================================================\n\n--    \u03bb> representaciones 3025\n--    [(0,55),(33,44)]\n--    (2.86 secs, 1,393,133,528 bytes)\n--    \u03bb> representaciones2 3025\n--    [(0,55),(33,44)]\n--    (0.00 secs, 867,944 bytes)\n--    \u03bb> representaciones3 3025\n--    [(0,55),(33,44)]\n--    (0.00 secs, 173,512 bytes)\n--    \u03bb> representaciones4 3025\n--    [(0,55),(33,44)]\n--    (0.00 secs, 423,424 bytes)\n--\n--    \u03bb> length (representaciones2 (10^10))\n--    6\n--    (3.38 secs, 2,188,903,544 bytes)\n--    \u03bb> length (representaciones3 (10^10))\n--    6\n--    (0.10 secs, 62,349,048 bytes)\n--    \u03bb> length (representaciones4 (10^10))\n--    6\n--    (0.11 secs, 48,052,360 bytes)\n--\n--    \u03bb> length (representaciones3 (4*10^12))\n--    7\n--    (1.85 secs, 1,222,007,176 bytes)\n--    \u03bb> length (representaciones4 (4*10^12))\n--    7\n--    (1.79 secs, 953,497,480 bytes)\n\n-- Definici\u00f3n de primosImparesConRepresentacionUnica\n-- =================================================\n\nprimosImparesConRepresentacionUnica :: [Integer]\nprimosImparesConRepresentacionUnica =\n  [x | x <- tail primes\n     , length (representaciones4 x) == 1]\n\n-- Definici\u00f3n de primos4nM1\n-- ========================\n\nprimos4nM1 :: [Integer]\nprimos4nM1 = [x | x <- primes\n                , x `mod` 4 == 1]\n\n-- Teorema de Navidad de Fermat\n-- ============================\n\n-- La propiedad es\nprop_teoremaDeNavidadDeFermat :: Positive Int -> Bool\nprop_teoremaDeNavidadDeFermat (Positive n) =\n  primosImparesConRepresentacionUnica !! n == primos4nM1 !! n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_teoremaDeNavidadDeFermat\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Verificaci\u00f3n                                                     --\n-- ---------------------------------------------------------------------\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = 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  it \"e4\" $\n    take 20 primosImparesConRepresentacionUnica `shouldBe`\n     [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]\n  it \"e5\" $\n    take 20 primos4nM1 `shouldBe`\n     [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    5 examples, 0 failures\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 math import floor, sqrt\nfrom timeit import Timer, default_timer\nfrom typing import Iterator\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\nfrom sympy import isprime\n\n# 1\u00aa definici\u00f3n de representaciones\n# =================================\n\ndef representaciones(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 definici\u00f3n de representaciones\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 definici\u00f3n de representaciones\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 representaciones(20) == [(2,4)]\n    assert representaciones(25) == [(0,5),(3,4)]\n    assert representaciones(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 = representaciones(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('representaciones(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# Definici\u00f3n de primosImparesConRepresentacionUnica\n# =================================================\n\n# primos() genera la lista de los primos. Por ejemplo,\n#    >>> list(islice(primos(), 10))\n#    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\ndef primos() -> Iterator[int]:\n    return (n for n in count() if isprime(n))\n\ndef primosImparesConRepresentacionUnica() -> Iterator[int]:\n    return (x for x in islice(primos(), 1, None)\n            if len(representaciones2(x)) == 1)\n\n# Verificaci\u00f3n de primosImparesConRepresentacionUnica\n# ===================================================\n\ndef test_primosImparesConRepresentacionUnica() -> None:\n    assert list(islice(primosImparesConRepresentacionUnica(), 20)) == \\\n        [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]\n    print(\"Verificado\")\n\n# La comprobaci\u00f3n es\n#    >>> test_primosImparesConRepresentacionUnica()\n#    Verificado\n\n# Definici\u00f3n de primos4nM1\n# ========================\n\ndef primos4nM1() -> Iterator[int]:\n    return (x for x in primos() if x % 4 == 1)\n\n# La comprobaci\u00f3n es\n#    >>> test_primos4nM1()\n#    Verificado\n\n# Verificaci\u00f3n de primos4nM1\n# ==========================\n\ndef test_primos4nM1() -> None:\n    assert list(islice(primos4nM1(), 20)) == \\\n        [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]\n    print(\"Verificado\")\n\n# Teorema de Navidad de Fermat\n# ============================\n\n# nth(i, n) es el n-\u00e9simo elemento del iterador i. Por ejemplo,\n#    nth(primos(), 4) == 11\ndef nth(i: Iterator[int], n: int) -> int:\n    return list(islice(i, n, n+1))[0]\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=300))\ndef test_teoremaDeNavidadDeFermat(n: int) -> None:\n    assert nth(primosImparesConRepresentacionUnica(), n) == nth(primos4nM1(), n)\n\n# La comprobaci\u00f3n es\n#    >>> test_teoremaDeNavidadDeFermat()\n#    >>>\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>El 25 de diciembre de 1640, en una carta a Mersenne, Fermat demostr\u00f3 la conjetura de Girard: todo primo de la forma 4n+1 puede expresarse de manera \u00fanica como suma de dos cuadrados. Por eso es conocido como el teorema de Navidad de Fermat. Definir las funciones representaciones :: Integer -> [(Integer,Integer)] primosImparesConRepresentacionUnica :: [Integer]&#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":"","_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\/8358"}],"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=8358"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8358\/revisions"}],"predecessor-version":[{"id":8409,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8358\/revisions\/8409"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8358"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8358"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8358"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}