{"id":1466,"date":"2011-07-27T10:47:23","date_gmt":"2011-07-27T10:47:23","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1466"},"modified":"2011-07-27T11:08:30","modified_gmt":"2011-07-27T11:08:30","slug":"descomposiciones-en-sumas-de-cuadrados-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/descomposiciones-en-sumas-de-cuadrados-en-haskell\/","title":{"rendered":"Descomposiciones en sumas de cuadrados en Haskell"},"content":{"rendered":"<p>Esta relaci\u00f3n de ejercicios, para la asignatura de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a>, se basa en el problema 19 de los desaf\u00edos matem\u00e1ticos de El Pa\u00eds titulado <a href=\"http:\/\/bit.ly\/qA8vQ0\">Cuadrados que suman grandes cifras<\/a> cuyo enunciado es el siguiente<\/p>\n<blockquote><p>\nLos n\u00fameros cuadrados (o cuadrados perfectos) son los cuadrados de los n\u00fameros naturales, es decir: 1 (1^2), 4 (2^2), 9 (3^2), 16 (4^2), 25 (5^2), etc\u00e9tera. En el problema de esta semana trataremos de descubrir de cu\u00e1ntas maneras distintas se puede escribir un n\u00famero dado como suma de cuatro cuadrados. Por ejemplo, el n\u00famero 39 se puede escribir de dos formas: 39=1+1+1+36 y 39=1+4+9+25. Observemos que se pueden repetir sumandos y que no contaremos como maneras distintas de escritura las que se obtienen al cambiar el orden de los sumandos.   <\/p>\n<p>Las preguntas concretas son: \u00bfDe cu\u00e1ntas formas distintas se puede escribir 2^2012 como suma de cuatro cuadrados? \u00bfY de cu\u00e1ntas formas se puede escribir 2^2011?\n<\/p><\/blockquote>\n<p>La relaci\u00f3n de ejercicios es la siguiente<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--    sumasNcuadrados :: Integer -> Integer -> [[Integer]]\r\n-- tal que (sumasNcuadrados x n) es la lista de las descomposiciones de\r\n-- x en sumas decrecientes de n cuadrados. Por ejemplo,\r\n--    sumasNcuadrados 39 4  ==  [[6,1,1,1],[5,3,2,1]]\r\n-- ---------------------------------------------------------------------\r\n\r\nsumasNcuadrados :: Integer -> Integer -> [[Integer]]\r\nsumasNcuadrados 0 _ = []\r\nsumasNcuadrados x 1 | a^2 == x  = [[a]] \r\n                    | otherwise = []\r\n                    where a = ceiling (sqrt (fromIntegral x))\r\nsumasNcuadrados x (n+1) = \r\n    [a:y:ys | a <- [x',x'-1..1],\r\n              (y:ys) <- sumasNcuadrados (x-a^2) n,\r\n              y <= a]\r\n        where x' = ceiling (sqrt (fromIntegral x))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n \r\n--    potenciaDe2ComoSumaDe4Cuadrados :: Integer -> [[Integer]]\r\n-- tal que (potenciaDe2ComoSumaDe4Cuadrados x) es la lista de las\r\n-- descomposiciones de 2^x en sumas decrecientes de n cuadrados. Por\r\n-- ejemplo, \r\n--    potenciaDe2ComoSumaDe4Cuadrados 6  ==  [[4,4,4,4]]\r\n-- ---------------------------------------------------------------------\r\n\r\npotenciaDe2ComoSumaDe4Cuadrados :: Integer -> [[Integer]]\r\npotenciaDe2ComoSumaDe4Cuadrados x =\r\n    sumasNcuadrados (2^x) 4\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n \r\n--    potenciasDe2ComoSumaDe4Cuadrados :: Integer -> Integer -> \r\n--                                        [(Integer,[[Integer]])]\r\n-- tal que (potenciasDe2ComoSumaDe4Cuadrados n m) es la lista de los\r\n-- pares (x,ys) tales que n <= x <= m e ys es la lista de las\r\n-- descomposiciones de 2^x en sumas decrecientes de n cuadrados. Por\r\n-- ejemplo, \r\n--    ghci> potenciasDe2ComoSumaDe4Cuadrados 4 5\r\n--    [(4,[[2,2,2,2]]),(5,[])]\r\n-- ---------------------------------------------------------------------\r\n\r\npotenciasDe2ComoSumaDe4Cuadrados :: Integer -> Integer -> \r\n                                    [(Integer,[[Integer]])]\r\npotenciasDe2ComoSumaDe4Cuadrados n m =\r\n    [(x,potenciaDe2ComoSumaDe4Cuadrados x) | x <- [n..m]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Usando la funci\u00f3n potenciasDe2ComoSumaDe4Cuadrados\r\n-- calcular la lista de las descomposiciones de 2^x en sumas\r\n-- decrecientes de n cuadrados, para x entre 1 y 10.\r\n-- ---------------------------------------------------------------------\r\n \r\n-- El c\u00e1lculo es\r\n--    ghci> potenciasDe2ComoSumaDe4Cuadrados 1 10\r\n--    [(1,[]),(2,[[1,1,1,1]]),            \r\n--     (3,[]),(4,[[2,2,2,2]]),            \r\n--     (5,[]),(6,[[4,4,4,4]]),            \r\n--     (7,[]),(8,[[8,8,8,8]]),            \r\n--     (9,[]),(10,[[16,16,16,16]])]       \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. A partir del c\u00e1lculo anterior conjeturar el valor de \r\n-- (potenciaDe2ComoSumaDe4Cuadrados x)) y usando la conjetura\r\n-- definir la funci\u00f3n \r\n--    potenciaDe2ComoSumaDe4Cuadrados' :: Integer -> [[Integer]]\r\n-- que sea equivalente a potenciaDe2ComoSumaDe4Cuadrados.\r\n-- ---------------------------------------------------------------------\r\n\r\npotenciaDe2ComoSumaDe4Cuadrados' :: Integer -> [[Integer]]\r\npotenciaDe2ComoSumaDe4Cuadrados' x \r\n    | odd x     = []\r\n    | otherwise = [[y,y,y,y]]\r\n    where y = 2^((x `div` 2) - 1)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n  \r\n--    conjetura :: Integer -> Integer -> Bool\r\n-- tal que (conjetura n m) se verifica si los valores de\r\n-- potenciaDe2ComoSumaDe4Cuadrados y potenciaDe2ComoSumaDe4Cuadrados'\r\n-- para todo x entre n y m.\r\n--\r\n-- Comprobar la conjetura para los valores entre 1 y 20.\r\n-- ---------------------------------------------------------------------\r\n\r\nconjetura :: Integer -> Integer -> Bool\r\nconjetura n m = \r\n    and [potenciaDe2ComoSumaDe4Cuadrados x == \r\n         potenciaDe2ComoSumaDe4Cuadrados' x\r\n        | x <- [n..m]]\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> conjetura 1 20\r\n--    True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Usando la conjetura, resolver el desaf\u00edo; es decir,\r\n-- responder a las preguntas \u00bfde cu\u00e1ntas formas distintas se puede\r\n-- escribir 2^2012 como suma de cuatro cuadrados? \u00bfY de cu\u00e1ntas formas\r\n-- se puede escribir 2^2011? \r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> length (potenciaDe2ComoSumaDe4Cuadrados' 2012)\r\n--    1\r\n--    ghci> length (potenciaDe2ComoSumaDe4Cuadrados' 2011)\r\n--    0\r\n<\/pre>\n<p>La demostraci\u00f3n se encuentra en <a href=\"http:\/\/bit.ly\/qufzvm\">Una \u00fanica suma posible de cuadrados<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Esta relaci\u00f3n de ejercicios, para la asignatura de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas, se basa en el problema 19 de los desaf\u00edos matem\u00e1ticos de El Pa\u00eds titulado Cuadrados que suman grandes cifras cuyo enunciado es el siguiente Los n\u00fameros cuadrados (o cuadrados perfectos) son los cuadrados de los n\u00fameros naturales, es decir: 1&#8230;<\/p>\n","protected":false},"author":2,"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":[5],"tags":[270],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1466"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=1466"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1466\/revisions"}],"predecessor-version":[{"id":1471,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1466\/revisions\/1471"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1466"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1466"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1466"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}