{"id":6409,"date":"2021-05-19T06:00:09","date_gmt":"2021-05-19T04:00:09","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6409"},"modified":"2021-05-26T10:59:34","modified_gmt":"2021-05-26T08:59:34","slug":"numeros-suma-de-dos-cuadrados","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numeros-suma-de-dos-cuadrados\/","title":{"rendered":"N\u00fameros suma de dos cuadrados"},"content":{"rendered":"

El enunciado del problema 3.3 de la Fase Local de la Olimpiada Matem\u00e1tica Espa\u00f1ola del 2004<\/a> es<\/p>\n

\n Hallad todas las posibles formas de escribir 2003 como suma de dos cuadrados de n\u00fameros enteros positivos.\n<\/p><\/blockquote>\n

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

\n   sonSumaDosCuadrados :: [Integer]\n<\/pre>\n
cuyos elementos son los n\u00fameros que se pueden expresar como suma de los cuadrados de dos n\u00fameros naturales. Por ejemplo,<\/p>\n
\n   take 6 sonSumaDosCuadrados      ==  [0,1,2,4,5,8]\n   sonSumaDosCuadrados !! (10^4)   ==  39593\n<\/pre>\n
Comprobar con QuickCheck las siguientes propiedades:<\/p>\n
    \n
  • La sucesi\u00f3n sonSumaDosCuadrados es infinita.<\/li>\n
  • Los elementos de sonSumaDosCuadrados no son congruentes con 3 m\u00f3dulo 4 (es decir, sus restos al dividirlo por 4 son distintos de 3).<\/li>\n<\/ul>\n
    Usando sonSumaDosCuadrados, resolver el problema propuesto; es decir, calcular todas las posibles formas de escribir 2003 como suma de dos cuadrados de n\u00fameros enteros positivos.<\/p>\n
    Soluciones<\/h4>\n
    <<\/p>\n
    pre lang=\u00bbhaskell\u00bb>
    \nimport Test.QuickCheck (Property, (==>), quickCheck)<\/p>\n
    — 1\u00aa soluci\u00f3n
    \n— ===========<\/p>\n
    sonSumaDosCuadrados :: [Integer]
    \nsonSumaDosCuadrados =
    \n  filter esSumaDeDosCuadrados [0..]<\/p>\n
    — (esSumaDeDosCuadrados) se verifica si n se puede escribir como la
    \n— suma de los cuadrados de dos n\u00fameros naturales. Por ejemplo,
    \n—    esSumaDeDosCuadrados 5  ==  True
    \n—    esSumaDeDosCuadrados 3  ==  False
    \nesSumaDeDosCuadrados :: Integer -> Bool
    \nesSumaDeDosCuadrados = not . null . descomposicionesSumaDosCuadrados<\/p>\n
    — (descomposicionesSumaDosCuadrados n) es la lista de pares de
    \n— cuadrados de n\u00fameros naturales (con la primera componente menor o
    \n— igual que la segunda) cuya suma es n. Por ejmplo,
    \n—    descomposicionesSumaDosCuadrados 3    == []
    \n—    descomposicionesSumaDosCuadrados 4    == [(0,4)]
    \n—    descomposicionesSumaDosCuadrados 5    == [(1,4)]
    \n—    descomposicionesSumaDosCuadrados 25   == [(0,25),(9,16)]
    \n—    descomposicionesSumaDosCuadrados 325  == [(1,324),(36,289),(100,225)]
    \n—    descomposicionesSumaDosCuadrados 1105 == [(16,1089),(81,1024),(144,961),(529,576)]
    \ndescomposicionesSumaDosCuadrados :: Integer -> [(Integer,Integer)]
    \ndescomposicionesSumaDosCuadrados n =
    \n  [(a,b) | a <- xs,
    \n           let b = n – a,
    \n           b elem<\/code> xs,
    \n           a <= b]
    \n  where xs = takeWhile (<= n) cuadrados<\/p>\n
    — cuadrados es la lista de los cuadrados. Por ejemplo,
    \n—    take 10 cuadrados  ==  [0,1,4,9,16,25,36,49,64,81]
    \ncuadrados :: [Integer]
    \ncuadrados = map (^2) [0..]<\/p>\n
    — 2\u00aa soluci\u00f3n
    \n— ===========<\/p>\n
    sonSumaDosCuadrados2 :: [Integer]
    \nsonSumaDosCuadrados2 =
    \n  filter esSumaDeDosCuadrados2 [0..]<\/p>\n
    esSumaDeDosCuadrados2 :: Integer -> Bool
    \nesSumaDeDosCuadrados2 = not . null . descomposicionesSumaDosCuadrados2<\/p>\n
    descomposicionesSumaDosCuadrados2 :: Integer -> [(Integer,Integer)]
    \ndescomposicionesSumaDosCuadrados2 n =
    \n  [(a,b) | a <- ys,
    \n           let b = n – a,
    \n           b elem<\/code> m : zs]
    \n  where m  = n div<\/code> 2
    \n        xs = takeWhile (<= n) cuadrados
    \n        (ys,zs) = span (<= m) xs<\/p>\n
    — 3\u00aa soluci\u00f3n
    \n— ==========<\/p>\n
    sonSumaDosCuadrados3 :: [Integer]
    \nsonSumaDosCuadrados3 =
    \n  mezclaTodas [[n^2+k^2 | k <- [n..]] | n <- [0..]]<\/p>\n
    — (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como
    \n— sus elementos son listas infinitas ordenadas. Por ejemplo,
    \n—    \u03bb> take 10 (mezclaTodas [[n,2n..] | n <- [2..]])\n--    [2,3,4,5,6,7,8,9,10,11]\n--    \u03bb> take 10 (mezclaTodas [[n,2<\/em>n..] | n <- [2,9..]])
    \n—    [2,4,6,8,9,10,12,14,16,18]<\/p>\n
    \n
    mezclaTodas :: Ord a => [[a]] -> [a]
    \nmezclaTodas = foldr1 xmezcla
    \n  where xmezcla (x:xs) ys = x : mezcla xs ys<\/p>\n
    — (mezcla xs ys) es la mezcla de las listas infinitas ordenadas xs es
    \n— ys. Por ejemplo,
    \n—    take 10 (mezcla [1,3..] [4,8..])  == [1,3,4,5,7,8,9,11,12,13]
    \nmezcla :: Ord a => [a] -> [a] -> [a]
    \nmezcla (x:xs) (y:ys) | x < y  = x : mezcla xs (y:ys)
    \n                     | x == y = x : mezcla xs ys
    \n                     | x > y  = y : mezcla (x:xs) ys<\/p>\n
    — Comprobaci\u00f3n de equivalencia
    \n— ============================<\/p>\n
    — La comprobaci\u00f3n es
    \n—    \u03bb> take 1000 sonSumaDosCuadrados == take 1000 sonSumaDosCuadrados2
    \n—    True
    \n—    \u03bb> take 1000 sonSumaDosCuadrados2 == take 1000 sonSumaDosCuadrados3
    \n—    True<\/p>\n
    — Comparaci\u00f3n de eficiencia
    \n— =========================<\/p>\n
    — La comparaci\u00f3n es
    \n—    \u03bb> sonSumaDosCuadrados !! (510^3)
    \n—    18973
    \n—    (2.29 secs, 266,485,976 bytes)
    \n—    \u03bb> sonSumaDosCuadrados2 !! (5<\/em>10^3)
    \n—    18973
    \n—    (1.01 secs, 473,019,976 bytes)
    \n—    \u03bb> sonSumaDosCuadrados3 !! (5*10^3)
    \n—    18973<\/p>\n
    —    (0.17 secs, 103,957,288 bytes)<\/h2>\n
    —    \u03bb> sonSumaDosCuadrados2 !! (510^4)
    \n—    216090
    \n—    (78.14 secs, 17,856,157,080 bytes)
    \n—    \u03bb> sonSumaDosCuadrados3 !! (5<\/em>10^4)
    \n—    216090
    \n—    (4.23 secs, 3,325,056,480 bytes)<\/p>\n
    — Propiedades
    \n— ===========<\/p>\n
    — La primera propiedad es
    \nprop_infinitud :: Integer -> Bool
    \nprop_infinitud n =
    \n  (not . null) (dropWhile (<= n) sonSumaDosCuadrados3)<\/p>\n
    — Su comprobaci\u00f3n es
    \n—    \u03bb> quickCheck prop_infinitud
    \n—    +++ OK, passed 100 tests.<\/p>\n
    — La segunda propiedad es
    \nprop_modulo4 :: Int -> Property
    \nprop_modulo4 k =
    \n  k >= 0 ==>
    \n  (sonSumaDosCuadrados3 !! k) mod<\/code> 4  \/= 3<\/p>\n
    — Su comprobaci\u00f3n es
    \n—    \u03bb> quickCheck prop_modulo4
    \n—    +++ OK, passed 100 tests.<\/p>\n
    — 4\u00aa soluci\u00f3n
    \n— ===========<\/p>\n
    — Basada en la 2\u00aa propiedad.<\/p>\n
    sonSumaDosCuadrados4 :: [Integer]
    \nsonSumaDosCuadrados4 =
    \n  filter esSumaDeDosCuadrados4 [0..]<\/p>\n
    esSumaDeDosCuadrados4 :: Integer -> Bool
    \nesSumaDeDosCuadrados4 = not . null . descomposicionesSumaDosCuadrados4<\/p>\n
    descomposicionesSumaDosCuadrados4 :: Integer -> [(Integer,Integer)]
    \ndescomposicionesSumaDosCuadrados4 n
    \n  | n mod<\/code> 4 == 3 = []
    \n  | otherwise      = [(a,b) | a <- ys,
    \n                              let b = n – a,
    \n                              b elem<\/code> m : zs]
    \n    where m  = n div<\/code> 2
    \n          xs = takeWhile (<= n) cuadrados
    \n          (ys,zs) = span (<= m) xs<\/p>\n
    — Comprobaci\u00f3n de equivalencia
    \n— ============================<\/p>\n
    — La comprobaci\u00f3n es
    \n—    \u03bb> take 1000 sonSumaDosCuadrados3 == take 1000 sonSumaDosCuadrados4
    \n—    True<\/p>\n
    — Comparaci\u00f3n de eficiencia
    \n— =========================<\/p>\n
    — La comparaci\u00f3n es
    \n—    \u03bb> sonSumaDosCuadrados2 !! (10^4)
    \n—    39593
    \n—    (3.60 secs, 1,413,851,720 bytes)
    \n—    \u03bb> sonSumaDosCuadrados3 !! (10^4)
    \n—    39593
    \n—    (0.42 secs, 284,603,104 bytes)
    \n—    \u03bb> sonSumaDosCuadrados4 !! (10^4)
    \n—    39593
    \n—    (2.58 secs, 1,043,995,480 bytes)<\/p>\n
    — C\u00e1lculo para resolver el problema
    \n— =================================<\/p>\n
    — El c\u00e1lculo es
    \n—    \u03bb> 2003 == head (dropWhile (<2003) sonSumaDosCuadrados3)
    \n—    False
    \n— Por tanto, no es posible escribir 2003 como suma de dos cuadrados de
    \n— n\u00fameros enteros positivos.<\/p>\n
    Nuevas soluciones<\/h4>\n
      \n
    • En los comentarios se pueden escribir nuevas soluciones.\n
    • El c\u00f3digo se debe escribir entre una l\u00ednea con <pre lang="haskell"> y otra con <\/pre>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
      El enunciado del problema 3.3 de la Fase Local de la Olimpiada Matem\u00e1tica Espa\u00f1ola del 2004 es Hallad todas las posibles formas de escribir 2003 como suma de dos cuadrados de n\u00fameros enteros positivos. Definir la sucesi\u00f3n sonSumaDosCuadrados :: [Integer] cuyos elementos son los n\u00fameros que se pueden expresar como suma de los cuadrados de…<\/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":[2],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6409"}],"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=6409"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6409\/revisions"}],"predecessor-version":[{"id":6486,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6409\/revisions\/6486"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6409"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6409"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6409"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}