{"id":2225,"date":"2016-03-14T06:00:03","date_gmt":"2016-03-14T04:00:03","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2225"},"modified":"2016-04-01T19:15:38","modified_gmt":"2016-04-01T17:15:38","slug":"primo-suma-de-dos-cuadrados","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/primo-suma-de-dos-cuadrados\/","title":{"rendered":"Primo suma de dos cuadrados"},"content":{"rendered":"<p>Definir la sucesi\u00f3n<\/p>\n<pre lang=\"text\">\n   primosSumaDe2Cuadrados :: [Integer]\n<\/pre>\n<p>cuyos elementos son los n\u00fameros primos que se pueden escribir como sumas de dos cuadrados. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 20 primosSumaDe2Cuadrados\n   [2,5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181]\n   \u03bb> primosSumaDe2Cuadrados !! (2*10^5)\n   5803241\n<\/pre>\n<p>En el ejemplo anterior,<\/p>\n<ul>\n<li>13 est\u00e1 en la sucesi\u00f3n porque es primo y 13 = 2\u00b2+3\u00b2.  <\/li>\n<li>11 no est\u00e1 en la sucesi\u00f3n porque no se puede escribir como suma de dos cuadrados (en efecto, 11-1=10, 11-2\u00b2=7 y 11-3\u00b2=2 no son cuadrados). <\/li>\n<li>20 no est\u00e1 en la sucesi\u00f3n porque, aunque es suma de dos cuadrados (20=4\u00b2+2\u00b2), no es primo. <\/li>\n<\/ul>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (primes)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nprimosSumaDe2Cuadrados1 :: [Integer]\nprimosSumaDe2Cuadrados1 =\n    [n | n <- primes,\n         esSumaDe2Cuadrados n]\n\nesSumaDe2Cuadrados :: Integer -> Bool\nesSumaDe2Cuadrados n = not (null (sumas2cuadrados n))\n\nsumas2cuadrados :: Integer -> [(Integer,Integer)]\nsumas2cuadrados n = \n    [(x,y) | x <- [1..ceiling (sqrt (fromIntegral n))],\n             let z = n - x^2,\n             esCuadrado z, \n             let y = raiz z,\n             x <= y]\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 x = floor (sqrt (fromIntegral x))\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nprimosSumaDe2Cuadrados2 :: [Integer]\nprimosSumaDe2Cuadrados2 =\n    2 : [n | n <- primes,\n             n `mod` 4 == 1]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> primosSumaDe2Cuadrados1 !! (2*10^3)\n--    38153\n--    (3.03 secs, 568,239,744 bytes)\n--    \u03bb> primosSumaDe2Cuadrados2 !! (2*10^3)\n--    38153\n--    (0.05 secs, 20,017,912 bytes)\n<\/pre>\n<h4>Referencias<\/h4>\n<ul>\n<li>N.J.A. Sloane, <a href=\"https:\/\/oeis.org\/A002313\">Sucesi\u00f3n A002313<\/a> de la OEIS.<\/li>\n<li>M. Bates, <a href=\"http:\/\/people.math.umass.edu\/~bates\/Primes.pdf\">Primes of the form x\u00b2 + ny\u00b2<\/a>&#8211;<\/li>\n<li>G. Xiao, <a href=\"http:\/\/wims.unice.fr\/~wims\/en_tool~number~twosquares.en.html\">Two squares<\/a>.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Definir la sucesi\u00f3n primosSumaDe2Cuadrados :: [Integer] cuyos elementos son los n\u00fameros primos que se pueden escribir como sumas de dos cuadrados. Por ejemplo, \u03bb> take 20 primosSumaDe2Cuadrados [2,5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181] \u03bb> primosSumaDe2Cuadrados !! (2*10^5) 5803241 En el ejemplo anterior, 13 est\u00e1 en la sucesi\u00f3n porque es primo y 13 = 2\u00b2+3\u00b2. 11 no est\u00e1 en la sucesi\u00f3n&#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":[322,8,282,183,89,181,141,173,236],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2225"}],"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=2225"}],"version-history":[{"count":8,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2225\/revisions"}],"predecessor-version":[{"id":2278,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2225\/revisions\/2278"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2225"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2225"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2225"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}