{"id":3437,"date":"2017-11-24T06:00:07","date_gmt":"2017-11-24T04:00:07","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3437"},"modified":"2017-12-04T07:49:42","modified_gmt":"2017-12-04T05:49:42","slug":"sumas-de-dos-cuadrados","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/sumas-de-dos-cuadrados\/","title":{"rendered":"Sumas de dos cuadrados"},"content":{"rendered":"<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   sumasDe2Cuadrados :: Integer -> [(Integer, Integer)]\n<\/pre>\n<p>tal que (sumasDe2Cuadrados n) es la lista de los pares de n\u00fameros tales que la suma de sus cuadrados es n y el primer elemento del par es mayor o igual que el segundo. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   sumasDe2Cuadrados 25                ==  [(5,0),(4,3)]\n   sumasDe2Cuadrados 32                ==  [(4,4)]\n   sumasDe2Cuadrados 55                ==  []\n   sumasDe2Cuadrados 850               ==  [(29,3),(27,11),(25,15)]\n   length (sumasDe2Cuadrados (10^12))  ==  7\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\n-- 1\u00aa definici\u00f3n\nsumasDe2Cuadrados1 :: Integer -> [(Integer, Integer)]\nsumasDe2Cuadrados1 n = \n  [(x,y) | x <- [n,n-1..0]\n         , y <- [0..x]\n         , x*x+y*y == n]\n\n-- 2\u00aa definici\u00f3n:\nsumasDe2Cuadrados2 :: Integer -> [(Integer, Integer)]\nsumasDe2Cuadrados2 n = \n  [(x,y) | x <- [a,a-1..0]\n         , y <- [0..x]\n         , x*x+y*y == n]\n  where a = (floor . sqrt . fromIntegral) n\n\n-- 3\u00aa definici\u00f3n\nsumasDe2Cuadrados3 :: Integer -> [(Integer, Integer)]\nsumasDe2Cuadrados3 n =\n  [(raizEntera x, raizEntera y)\n  | y <- takeWhile (<= n `div` 2) cuadrados\n  , let x = n - y\n  , esCuadrado x]\n\ncuadrados :: [Integer]\ncuadrados = map (^2) [0..]\n\nesCuadrado :: Integer -> Bool\nesCuadrado x =\n  x == y * y\n  where y = raizEntera x\n  \nraizEntera :: Integer -> Integer\nraizEntera x =\n  (floor . sqrt . fromIntegral) x\n\n-- 4\u00aa definici\u00f3n\nsumasDe2Cuadrados4 :: Integer -> [(Integer, Integer)]\nsumasDe2Cuadrados4 n = aux ((floor . sqrt . fromIntegral) n) 0 \n  where aux x y | x < y          = [] \n                | x*x + y*y <  n = aux x (y+1)\n                | x*x + y*y == n = (x,y) : aux (x-1) (y+1)\n                | otherwise      = aux (x-1) y\n\n-- Comparaci\u00f3n de eficiencia\n--    \u03bb> sumasDe2Cuadrados1 2020\n--    [(42,16),(38,24)]\n--    (4.29 secs, 621,601,336 bytes)\n--    \u03bb> sumasDe2Cuadrados2 2020\n--    [(42,16),(38,24)]\n--    (0.01 secs, 488,496 bytes)\n--    \u03bb> sumasDe2Cuadrados3 2020\n--    [(42,16),(38,24)]\n--    (0.02 secs, 197,256 bytes)\n--    \u03bb> sumasDe2Cuadrados4 2020\n--    [(42,16),(38,24)]\n--    (0.01 secs, 175,088 bytes)\n--\n--    \u03bb> length (sumasDe2Cuadrados2 48612265)\n--    32\n--    (51.25 secs, 7,395,035,904 bytes)\n--    \u03bb> length (sumasDe2Cuadrados3 48612265)\n--    32\n--    (0.06 secs, 8,368,296 bytes)\n--    \u03bb> length (sumasDe2Cuadrados4 48612265)\n--    32\n--    (0.04 secs, 3,483,168 bytes)\n--    \n--    \u03bb> length (sumasDe2Cuadrados3 (10^12))\n--    7\n--    (7.32 secs, 1,137,167,688 bytes)\n--    \u03bb> length (sumasDe2Cuadrados4 (10^12))\n--    7\n--    (3.64 secs, 480,776,736 bytes)\n<\/pre>\n<p>[\/schedule]<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Definir la funci\u00f3n sumasDe2Cuadrados :: Integer -> [(Integer, Integer)] tal que (sumasDe2Cuadrados n) es la lista de los pares de n\u00fameros tales que la suma de sus cuadrados es n y el primer elemento del par es mayor o igual que el segundo. Por ejemplo, sumasDe2Cuadrados 25 == [(5,0),(4,3)] sumasDe2Cuadrados 32 == [(4,4)] sumasDe2Cuadrados 55&#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":[7],"tags":[8,282,183,10,11,6,236,34],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3437"}],"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=3437"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3437\/revisions"}],"predecessor-version":[{"id":3480,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3437\/revisions\/3480"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3437"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3437"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3437"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}