{"id":1803,"date":"2012-01-01T20:05:37","date_gmt":"2012-01-01T20:05:37","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1803"},"modified":"2013-03-08T05:48:57","modified_gmt":"2013-03-08T05:48:57","slug":"ultimos-dos-digitos-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/ultimos-dos-digitos-en-haskell\/","title":{"rendered":"\u00daltimos dos d\u00edgitos de (1+5^(2*n+1))\/6 en Haskell"},"content":{"rendered":"<p>Ayer <a href=\"http:\/\/twitter.com\/#!\/BenVitale\">Benjamin Vitale<\/a> plante\u00f3 el problema <a href=\"http:\/\/checkthis.com\/t8o1\">\u00daltimos dos d\u00edgitos de (1+5^(2n+1))\/6<\/a> que consiste en demostrar que para cualquier n \u2265 1 los \u00faltimos dos d\u00edgitos de <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=%5Cfrac%7B1%2B5%5E%7B2n%2B1%7D%7D%7B6%7D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"&#92;frac{1+5^{2n+1}}{6}\" class=\"latex\" \/> son 21. <\/p>\n<p>A partir del problema he elaborado la siguiente relaci\u00f3n de ejercicios para <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\">Inform\u00e1tica (de 1\u00ba del Grado en Matem\u00e1ticas)<\/a>.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Librer\u00edas auxiliares                                               --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n \r\n--    f :: Integer -> Integer\r\n-- tal que f(n) = (1+5^(2*n+1))\/6 y calcular el valor de f(n) para n\r\n-- desde 1 hasta 6.\r\n-- ---------------------------------------------------------------------\r\n\r\nf :: Integer -> Integer\r\nf n = (1+5^(2*n+1)) `div` 6\r\n\r\n-- El c\u00e1lculo es \r\n--    ghci> [f n | n <- [1..6]]\r\n--    [21,521,13021,325521,8138021,203450521]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    dos_ultimos :: Integer -> Integer\r\n-- tal que (dos_ultimos x) es el n\u00famero formado con los \u00faltimos d\u00edgitos\r\n-- de x. Por ejemplo,\r\n--    dos_ultimos 53579  ==  79\r\n-- ---------------------------------------------------------------------\r\n\r\ndos_ultimos :: Integer -> Integer\r\ndos_ultimos x = x `mod` 100 \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Comprobar con QuickCheck que para cualquier n \u2265 1 los\r\n-- \u00faltimos dos d\u00edgitos de (1+5^(2n+1))\/6 son 21.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_dos_ultimos :: Integer -> Bool\r\nprop_dos_ultimos n = dos_ultimos (f n') == 21\r\n    where n' = 1 + abs n\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_dos_ultimos\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Demostrar, por inducci\u00f3n, que para cualquier n \u2265 1 los\r\n-- \u00faltimos dos d\u00edgitos de (1+5^(2n+1))\/6 son 21.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Como f(n) = (1+5^(2n+1))\/6, lo que hay que demostrar es que, para\r\n-- cualquier n \u2265 1, existe un n\u00famero natural x tal f(n) = 100*x+21. Lo\r\n-- haremos por inducci\u00f3n en n. \r\n-- \r\n-- (Base n=1) h(1) = 21 = 100*0+21\r\n-- \r\n-- (Paso n --> n+1) La hip\u00f3tesis de inducci\u00f3n, es que existe un y tal\r\n-- que \r\n--    f(n) = 100*y+21\r\n-- Luego, por definici\u00f3n de f, \r\n--    (1+5^(2*n+1))\/6 = 100*y+21              \r\n-- y, despejando,\r\n--    5^(2*n+1) = 600*y+125            (1)\r\n-- Adem\u00e1s, por definici\u00f3n de f,\r\n--    f(n+1) = (1+5^(2*(n+1)+1))\/6\r\n--           = (1+5^((2*n+1)+2))\/6\r\n--           = (1+5^(2*n+1)*5^2)\/6\r\n--           = (1+(600*y+125)*25)\/6    [por (1)]\r\n--           = (1+600*25*y+125*25)\/6\r\n--           = 100*25*y+521\r\n--           = 100*(25*y+5)+21         \r\n--           = 100*x+21,               [con x = 25*y+5]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. A partir de la demostraci\u00f3n anterior, definir por\r\n-- recursi\u00f3n una funci\u00f3n\r\n--    g :: Integer -> Integer\r\n-- tal que g es equivalente a f.\r\n-- ---------------------------------------------------------------------\r\n\r\ng :: Integer -> Integer\r\ng 1 = 21\r\ng (n+1) = 100*(25*x+5)+21\r\n           where x = ((f n) - 21) `div` 100\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Comprobar con QuickCheck que que las funciones f y g son\r\n-- equivalentes, para n \u2265 1. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es \r\nprop_equivalencia :: Integer -> Bool\r\nprop_equivalencia n = f n' == g n' \r\n    where n' = 1 + abs n\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_equivalencia\r\n--    +++ OK, passed 100 tests.\r\n<\/pre>\n<p>Nota: Otra demostraci\u00f3n, usando aritm\u00e9tica modular, es la realizada por <a href=\"http:\/\/twitter.com\/joseanpg\">@joseanpg<\/a> que se puede leer <a href=\"http:\/\/tl.gd\/f2sf8j\">aqu\u00ed<\/a>. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Ayer Benjamin Vitale plante\u00f3 el problema \u00daltimos dos d\u00edgitos de (1+5^(2n+1))\/6 que consiste en demostrar que para cualquier n \u2265 1 los \u00faltimos dos d\u00edgitos de son 21. A partir del problema he elaborado la siguiente relaci\u00f3n de ejercicios para Inform\u00e1tica (de 1\u00ba del Grado en Matem\u00e1ticas).<\/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":[5],"tags":[270,126],"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\/1803"}],"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=1803"}],"version-history":[{"count":8,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1803\/revisions"}],"predecessor-version":[{"id":2876,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1803\/revisions\/2876"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1803"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1803"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1803"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}