{"id":4486,"date":"2018-12-31T06:00:19","date_gmt":"2018-12-31T04:00:19","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4486"},"modified":"2021-04-25T16:24:05","modified_gmt":"2021-04-25T14:24:05","slug":"el-teorema-de-navidad-de-fermat-2018","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/el-teorema-de-navidad-de-fermat-2018\/","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>(representaciones n) es la lista de pares de n\u00fameros naturales (x,y) tales que n = x^2 + y^2 con x &lt;= y. 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>primosImparesConRepresentacionUnica 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 (x,y) con x &lt;= y. 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>primos4nM1 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>Comprobar con QuickCheck el torema de Navidad de Fermat; es decir, que para todo n\u00famero n, los n-\u00e9simos elementos de primosImparesConRepresentacionUnica y de primos4nM1 son iguales.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (primes)\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-- (esCuadrado 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<\/pre>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\n&#8211; \u00a1Cu\u00e1ndo llegar\u00e1 otro d\u00eda!<br \/>\n&#8211; Hoy es siempre todav\u00eda.<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\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":[4],"tags":[161,8,30,282,183,28,89,173,6,236,45,146],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4486"}],"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=4486"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4486\/revisions"}],"predecessor-version":[{"id":4525,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4486\/revisions\/4525"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4486"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4486"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4486"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}