{"id":5387,"date":"2016-04-01T11:42:11","date_gmt":"2016-04-01T09:42:11","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5387"},"modified":"2016-04-02T11:45:58","modified_gmt":"2016-04-02T09:45:58","slug":"i1m2015-los-numeros-de-lychrel-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-los-numeros-de-lychrel-en-haskell\/","title":{"rendered":"I1M2015: Los n\u00fameros de Lychrel en Haskell"},"content":{"rendered":"<p>En la segunda parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 29 sobre los n\u00fameros de Lychrel.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- Seg\u00fan la Wikipedia, un n\u00famero de Lychrel es un n\u00famero natural para\n-- el que nunca se obtiene un capic\u00faa mediante el proceso de invertir\n-- las cifras y sumar los dos n\u00fameros. Por ejemplo, los siguientes\n-- n\u00fameros no son n\u00fameros de Lychrel:\n--    * 56, ya que en un paso se obtiene un capic\u00faa: 56+65=121.\n--    * 57, ya que en dos pasos se obtiene un capic\u00faa: 57+75=132,\n--      132+231=363\n--    * 59, ya que en dos pasos se obtiene un capic\u00faa: 59+95=154,\n--      154+451=605, 605+506=1111\n--    * 89, ya que en 24 pasos se obtiene un capic\u00faa.\n-- En esta relaci\u00f3n vamos a buscar el primer n\u00famero de Lychrel.\n\n-- ---------------------------------------------------------------------\n-- Librer\u00edas auxiliares                                               --\n-- ---------------------------------------------------------------------\n\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    esCapicua :: Integer -> Bool\n-- tal que (esCapicua x) se verifica si x es capic\u00faa. Por ejemplo,\n--    esCapicua 252  ==  True\n--    esCapicua 253  ==  False\n-- ---------------------------------------------------------------------\n\nesCapicua :: Integer -> Bool\nesCapicua x = x1 == reverse x1\n    where x1 = show x\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    inverso :: Integer -> Integer\n-- tal que (inverso x) es el n\u00famero obtenido escribiendo las cifras de x\n-- en orden inverso. Por ejemplo,\n--    inverso 253  ==  352\n-- ---------------------------------------------------------------------\n\ninverso :: Integer -> Integer\ninverso = read . reverse . show\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    siguiente :: Integer -> Integer\n-- tal que (siguiente x) es el n\u00famero obtenido sum\u00e1ndole a x su\n-- inverso. Por ejemplo,\n--    siguiente 253  ==  605\n-- ---------------------------------------------------------------------\n\nsiguiente :: Integer -> Integer\nsiguiente x = x + inverso x\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    busquedaDeCapicua :: Integer -> [Integer]\n-- tal que (busquedaDeCapicua x) es la lista de los n\u00fameros tal que el\n-- primero es x, el segundo es (siguiente de x) y as\u00ed sucesivamente\n-- hasta que se alcanza un capic\u00faa. Por ejemplo,\n--    busquedaDeCapicua 253  ==  [253,605,1111]\n-- ---------------------------------------------------------------------\n\nbusquedaDeCapicua :: Integer -> [Integer]\nbusquedaDeCapicua x | esCapicua x = [x]\n                    | otherwise   = x : busquedaDeCapicua (siguiente x)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    capicuaFinal :: Integer -> Integer\n-- tal que (capicuaFinal x) es la capic\u00faa con la que termina la b\u00fasqueda\n-- de capic\u00faa a partir de x. Por ejemplo,\n--    capicuaFinal 253  ==  1111\n-- ---------------------------------------------------------------------\n\ncapicuaFinal :: Integer -> Integer\ncapicuaFinal x = last (busquedaDeCapicua x)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    orden :: Integer -> Integer\n-- tal que (orden x) es el n\u00famero de veces que se repite el proceso de\n-- calcular el inverso a partir de x hasta alcanzar un n\u00famero\n-- capic\u00faa. Por ejemplo,\n--    orden 253  ==  2\n-- ---------------------------------------------------------------------\n\norden :: Integer -> Integer\norden x | esCapicua x = 0\n        | otherwise   = 1 + orden (siguiente x)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    ordenMayor :: Integer -> Integer -> Bool\n-- tal que (ordenMayor x n) se verifica si el orden de x es mayor o\n-- igual que n. Dar la definici\u00f3n sin necesidad de evaluar el orden de\n-- x. Por ejemplo,\n--    ghci> ordenMayor 1186060307891929990 2\n--    True\n--    ghci> orden 1186060307891929990\n--    261\n-- ---------------------------------------------------------------------\n\nordenMayor :: Integer -> Integer -> Bool\nordenMayor x n | esCapicua x = n == 0\n               | n <= 0      = True\n               | otherwise   = ordenMayor (siguiente x) (n-1)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    ordenEntre :: Integer -> Integer -> [Integer]\n-- tal que (ordenEntre m n) es la lista de los elementos cuyo orden es\n-- mayor o igual que m y menor que n. Por ejemplo,\n--    take 5 (ordenEntre 10 11)  ==  [829,928,9059,9149,9239]\n-- ---------------------------------------------------------------------\n\nordenEntre :: Integer -> Integer -> [Integer]\nordenEntre m n = [x | x <- [1..], ordenMayor x m, not (ordenMayor x n)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n\n--    menorDeOrdenMayor :: Integer -> Integer\n-- tal que (menorDeOrdenMayor n) es el menor elemento cuyo orden es\n-- mayor que n. Por ejemplo,\n--    menorDeOrdenMayor 2   ==  19\n--    menorDeOrdenMayor 20  ==  89\n-- ---------------------------------------------------------------------\n\nmenorDeOrdenMayor :: Integer -> Integer\nmenorDeOrdenMayor n = head [x | x <- [1..], ordenMayor x n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n \n--    menoresdDeOrdenMayor :: Integer -> [(Integer,Integer)]\n-- tal que (menoresdDeOrdenMayor m) es la lista de los pares (n,x) tales\n-- que n es un n\u00famero entre 1 y m y x es el menor elemento de orden\n-- mayor que n. Por ejemplo,\n--    menoresdDeOrdenMayor 5  ==  [(1,10),(2,19),(3,59),(4,69),(5,79)]\n-- ---------------------------------------------------------------------\n\nmenoresdDeOrdenMayor :: Integer -> [(Integer,Integer)]\nmenoresdDeOrdenMayor m = [(n,menorDeOrdenMayor n) | n <- [1..m]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. A la vista de los resultados de (menoresdDeOrdenMayor 5)\n-- conjeturar sobre la \u00faltima cifra de menorDeOrdenMayor.\n-- ---------------------------------------------------------------------\n\n-- Soluci\u00f3n: La conjetura es que para n mayor que 1, la \u00faltima cifra de\n-- (menorDeOrdenMayor n) es 9. \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Decidir con QuickCheck la conjetura.\n-- ---------------------------------------------------------------------\n\n-- La conjetura es\nprop_menorDeOrdenMayor :: Integer -> Property\nprop_menorDeOrdenMayor n =\n    n > 1 ==> menorDeOrdenMayor n `mod` 10 == 9\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_menorDeOrdenMayor\n--    *** Failed! Falsifiable (after 22 tests and 2 shrinks):  \n--    25\n\n-- Se puede comprobar que 25 es un contraejemplo,\n--    ghci> menorDeOrdenMayor 25\n--    196\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Calcular (menoresdDeOrdenMayor 50)\n-- ---------------------------------------------------------------------\n\n-- Soluci\u00f3n: El c\u00e1lculo es\n--    ghci> menoresdDeOrdenMayor 50\n--    [(1,10),(2,19),(3,59),(4,69),(5,79),(6,79),(7,89),(8,89),(9,89),\n--     (10,89),(11,89),(12,89),(13,89),(14,89),(15,89),(16,89),(17,89),\n--     (18,89),(19,89),(20,89),(21,89),(22,89),(23,89),(24,89),(25,196),\n--     (26,196),(27,196),(28,196),(29,196),(30,196),(31,196),(32,196),\n--     (33,196),(34,196),(35,196),(36,196),(37,196),(38,196),(39,196),\n--     (40,196),(41,196),(42,196),(43,196),(44,196),(45,196),(46,196),\n--     (47,196),(48,196),(49,196),(50,196)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. A la vista de (menoresdDeOrdenMayor 50), conjeturar el\n-- orden de 196. \n-- ---------------------------------------------------------------------\n\n-- Soluci\u00f3n: El orden de 196 es infinito y, por tanto, 196 es un n\u00famero\n-- del Lychrel.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Comprobar con QuickCheck la conjetura sobre el orden de\n-- 196. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_ordenDe196 n =\n    ordenMayor 196 n\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_ordenDe196\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Nota. En el ejercicio anterior s\u00f3lo se ha comprobado la conjetura de\n-- que 196 es un n\u00famero de Lychrel. Otra cuesti\u00f3n distinta es\n-- probarla. Hasta la fecha, no se conoce ninguna demostraci\u00f3n ni\n-- refutaci\u00f3n de la conjetura 196.\n-- ---------------------------------------------------------------------\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 29 sobre los n\u00fameros de Lychrel. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/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":[250],"tags":[270,310],"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\/5387"}],"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=5387"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5387\/revisions"}],"predecessor-version":[{"id":5392,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5387\/revisions\/5392"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5387"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5387"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5387"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}