{"id":406,"date":"2010-08-13T09:52:09","date_gmt":"2010-08-13T09:52:09","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/numeros-de-lychrel\/"},"modified":"2015-04-30T23:01:21","modified_gmt":"2015-04-30T21:01:21","slug":"numeros-de-lychrel","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/numeros-de-lychrel\/","title":{"rendered":"N\u00fameros de Lychrel"},"content":{"rendered":"<p>Seg\u00fan la Wikipedia, un <a href=\"http:\/\/en.wikipedia.org\/wiki\/Lychrel_number\">n\u00famero de Lychrel<\/a> es un n\u00famero natural para el que nunca se obtiene un capic\u00faa mediante el proceso de invertir las cifras y sumar los dos n\u00fameros. Por ejemplo, los siguientes n\u00fameros no son n\u00fameros de Lychrel:<\/p>\n<ul>\n<li> 56, ya que en un paso se obtiene un capic\u00faa: 56+65=121.\n<li> 57, ya que en dos pasos se obtiene un capic\u00faa: 57+75=132, 132+231=363\n<li> 59, ya que en dos pasos se obtiene un capic\u00faa: 59+95=154, 154+451=605, 605+506=1111\n<li> 89, ya que en 24 pasos se obtiene un capic\u00faa.\n<\/ul>\n<p>En este ejercicio, pensado para la asignatura de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/\">Inform\u00e1tica (del Grado de Matem\u00e1ticas)<\/a> vamos a buscar con Haskell el primer n\u00famero de Lychrel.<br \/>\n<!--more--><br \/>\nLa idea del ejercicio surgi\u00f3 de la lectura del art\u00edculo <a href=\"http:\/\/gaussianos.com\/la-conjetura-del-196\/\">La conjetura del 196<\/a>.<\/p>\n<p>El c\u00f3digo Haskell del ejercicio resuelto es el siguiente:<\/p>\n<pre lang=\"haskell\">\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 = x' == reverse x'\n    where x' = 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--    *Main> :set +s\n--    *Main> ordenMayor 1186060307891929990 2\n--    True\n--    (0.00 secs, 0 bytes)\n--    *Main> orden 1186060307891929990\n--    261\n--    (0.05 secs, 9431600 bytes)\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 ==> [last (show (menorDeOrdenMayor n))] == \"9\"\n\n-- La comprobaci\u00f3n es\n--    *Main> 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--    *Main> menorDeOrdenMayor 25\n--    196\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Calcular (menoresdDeOrdenMayor 50)\n-- ---------------------------------------------------------------------\n\n-- Soluci\u00f3n: El c\u00e1lculo es\n--    *Main> 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--    *Main> quickCheck prop_ordenDe196\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p>Nota. En el ejercicio anterior s\u00f3lo se ha comprobado la conjetura de que 196 es un n\u00famero de Lychrel sobre una bater\u00eda de ejemoplos. Otra cuesti\u00f3n distinta es probarla o refutarla. Hasta la fecha, no se conoce ninguna demostraci\u00f3n ni refutaci\u00f3n de la conjetura 196. Tampoco se ha demostrado ni refutado la existencia de n\u00fameros de Lychrel.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Seg\u00fan la Wikipedia, un n\u00famero de Lychrel es un n\u00famero natural para el que nunca se obtiene un capic\u00faa mediante el proceso de invertir las cifras y sumar los dos n\u00fameros. Por ejemplo, los siguientes n\u00fameros no son n\u00fameros de Lychrel: 56, ya que en un paso se obtiene un capic\u00faa: 56+65=121. 57, ya que&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","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":[84,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\/406"}],"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=406"}],"version-history":[{"count":7,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/406\/revisions"}],"predecessor-version":[{"id":4884,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/406\/revisions\/4884"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}