{"id":2452,"date":"2013-01-07T07:01:38","date_gmt":"2013-01-07T07:01:38","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2452"},"modified":"2013-03-08T05:47:35","modified_gmt":"2013-03-08T05:47:35","slug":"representacion-de-2n-como-7x2y2-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/representacion-de-2n-como-7x2y2-en-haskell\/","title":{"rendered":"Representaci\u00f3n de 2\u207f como 7x\u00b2+y\u00b2 (con x e y impares) en Haskell"},"content":{"rendered":"

En la Olimpiada Matem\u00e1tica de Mosc\u00fa del 1988 se propuso el siguiente problema:<\/p>\n

\nSi \"n, entonces \"2^n\" se puede representar como \"2^n con x e y impares.\n<\/p><\/blockquote>\n

En la siguiente relaci\u00f3n de ejercicios (elaborada para la asignatura de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a>) se resuelve el problema con Haskell.
\n<\/p>\n

\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--     paresDeImpares :: [(Integer,Integer)]\r\n-- tal que paresDeImpares es la lista de pares de n\u00fameros impares. Por\r\n-- ejemplo,  \r\n--    ghci> take 10 paresDeImpares\r\n--    [(1,1),(1,3),(3,1),(1,5),(3,3),(5,1),(1,7),(3,5),(5,3),(7,1)]\r\n-- ---------------------------------------------------------------------\r\n\r\nparesDeImpares :: [(Integer,Integer)]\r\nparesDeImpares = \r\n    [(x,y) | n <- [1..], x <- [1,3..n], let y = n-x, odd y]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    solucion1 :: Integer -> (Integer,Integer)\r\n-- tal que (solucion1 n) es una soluci\u00f3n de la ecuaci\u00f3n 2^n =\r\n-- 7*x^2+y^2. Por ejemplo, \r\n--    solucion1 3  ==  (1,1)\r\n--    solucion1 8  ==  (5,9)\r\n-- ---------------------------------------------------------------------\r\n\r\nsolucion1 :: Integer -> (Integer,Integer)\r\nsolucion1 n = \r\n    head [(x,y) | (x,y) <- paresDeImpares, 2^n == 7*x^2+y^2]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Calcular las soluciones de 2^n = 7*x^2+y^2 para n entre\r\n-- 3 y 10.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> [(n,solucion1 n) | n <- [3..10]]\r\n--    [(3,(1,1)), (4,(1,3)),(5,(1,5)), (6,(3,1)),\r\n--     (7,(1,11)),(8,(5,9)),(9,(7,13)),(10,(3,31))]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. A partir del c\u00e1lculo anterior conjeturar c\u00f3mo se obtiene\r\n-- la soluci\u00f3n de m+1 a partir de la de m.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Sean (x,y) y (x',y') las soluciones de 2^n = 7*x^2+y^2  cuando n es m\r\n-- y m+1, respectivamente. Se trata de encontrar c\u00f3mo obtener (x',y') a\r\n-- partir de (x,y).\r\n-- \r\n-- A partir de las soluciones anteriores podemos obtener la siguiente\r\n-- tabla\r\n--\r\n--     n | x |  y | (x+y)\/2 | |7x-y|\/2 | |x-y|\/2 | (7x+y)\/2\r\n--   ----+---+----+---------+----------+---------+---------- \r\n--     3 | 1 |  1 | 1       | 3        |         |\r\n--     4 | 1 |  3 |         |          | 1       | 5\r\n--     5 | 1 |  5 | 3       | 1        |         |  \r\n--     6 | 3 |  1 |         |          | 1       | 11\r\n--     7 | 1 | 11 |         |          | 5       | 9\r\n--     8 | 5 |  9 | 7       | 13       |         | \r\n--     9 | 7 | 13 |         |          | 3       | 31\r\n--    10 | 3 | 31 | 17      | 5        |         | \r\n-- \r\n-- Se observa que x' = (x+y)\/2 para m en {3,5,8}; es decir, en los\r\n-- casos en que (x+y)\/2 es impar. En estos casos, y' = |7x-y|\/2.\r\n-- \r\n-- En el caso de que (x+y)\/2 es par (es decir para m en {4,6,7,9}), se\r\n-- tiene que x' = |x-y|\/2 e y' = (7x+y)\/2. \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir, usando la conjetura de ejercicio 4, la funci\u00f3n\r\n--    solucion2 :: Integer -> (Integer,Integer)\r\n-- tal que (solucion2 n) es una soluci\u00f3n de la ecuaci\u00f3n 2^n =\r\n-- 7*x^2+y^2. Por ejemplo, \r\n--    solucion2 3  ==  (1,1)\r\n--    solucion2 8  ==  (5,9)\r\n-- ---------------------------------------------------------------------\r\n\r\nsolucion2 :: Integer -> (Integer,Integer)\r\nsolucion2 3 = (1,1)\r\nsolucion2 n | odd media = (media, abs (7*x-y) `div` 2)\r\n            | otherwise  = (abs (x-y) `div` 2, (7*x+y) `div` 2)\r\n            where (x,y) = solucion2 (n-1)\r\n                  media = (x+y) `div` 2\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Comprobar la equivalencia de las funciones solucion1 y\r\n-- solucion2 para n entre 3 y 10.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> and [solucion1 n == solucion2 n | n <- [3..10]]\r\n--    True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Comparar la eficiencia de las funciones solucion1 y\r\n-- solucion2 para n = 28.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La comparaci\u00f3n es\r\n--    ghci> solucion1 28\r\n--    (181,16377)\r\n--    (299.50 secs, 42599321084 bytes)\r\n--    ghci> solucion2 28\r\n--    (181,16377)\r\n--    (0.00 secs, 525644 bytes)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Demostrar que la solucion2 es correcta; es decir, que\r\n-- para n >= 3, si (solucion2 n) es (x,y) entonces 2^n = 7*x^2+y^2.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Se demuestra por inducci\u00f3n en n.\r\n-- \r\n-- Base (n=3). Para n=3, (solucion2 n) es (1,1) y 2^3 = 7*1^2+1^2.\r\n--\r\n-- Paso. Supongamos que se cumple para n; es decir que (solucion2 n) es\r\n-- (x,y) y 2^n = 7*x^2+y^2. Sea (u,v) = (solucion2 (n+1)). hay que\r\n-- demostrar que 2^(n+1) = 7*u^2+v^2. Distinguiremos dos casos seg\u00fan la\r\n-- paridad de (x+y)\/2.\r\n-- \r\n-- Caso 1. Supongamos que (x+y)\/2 es impar, entonces u = (x+y)\/2 y \r\n-- v = |7x-y|\/2. Por tanto,\r\n--     7*u^2+v^2 = 7*((x+y)\/2)^2 + (|7x-y|\/2)^2\r\n--               = 7*(x^2+2xy+y^2)\/4 + (49x^2-14xy+y^2)\/4\r\n--               = (56x^2+8y^2)\/4\r\n--               = 14x^2+2y^2\r\n--               = 2(7x^2+y^2)\r\n--               = 2*2^n             [por la hip\u00f3tesis de inducci\u00f3n]\r\n--               = 2^(n+1)\r\n-- \r\n-- Caso 2. Supongamos que (x+y)\/2 es par, entonces u = |x-y|\/2 y \r\n-- v = (7x+y)\/2. Por tanto,\r\n--     7*u^2+v^2 = 7*(|x-y|\/2)^2 + ((7x+y)\/2)^2\r\n--               = 7*(x^2-2xy+y^2)\/4 + (49x^2+14xy+y^2)\/4\r\n--               = (56x^2+8y^2)\/4\r\n--               = 14x^2+2y^2\r\n--               = 2(7x^2+y^2)\r\n--               = 2*2^n             [por la hip\u00f3tesis de inducci\u00f3n]\r\n--               = 2^(n+1)\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
En la Olimpiada Matem\u00e1tica de Mosc\u00fa del 1988 se propuso el siguiente problema: Si , entonces se puede representar como con x e y impares. En la siguiente relaci\u00f3n de ejercicios (elaborada para la asignatura de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas) se resuelve el problema con Haskell.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[1],"tags":[27,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\/2452"}],"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=2452"}],"version-history":[{"count":12,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2452\/revisions"}],"predecessor-version":[{"id":2710,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2452\/revisions\/2710"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2452"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2452"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2452"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}