{"id":7500,"date":"2022-11-07T06:00:36","date_gmt":"2022-11-07T04:00:36","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7500"},"modified":"2022-12-14T11:51:21","modified_gmt":"2022-12-14T09:51:21","slug":"numeros-de-lychrel","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numeros-de-lychrel\/","title":{"rendered":"N\u00fameros de Lychrel"},"content":{"rendered":"

Un n\u00famero de Lychrel<\/a> es un n\u00famero 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:
\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, 132+231=363
\n+ 59, ya que en dos pasos se obtiene un capic\u00faa: 59+95=154, 154+451=605, 605+506=1111
\n+ 89, ya que en 24 pasos se obtiene un capic\u00faa.
\nEn esta serie de ejercicios vamos a buscar el primer n\u00famero de Lychrel.<\/p>\n

Ejercicio 1.<\/strong> Definir la funci\u00f3n<\/p>\n

\n   esCapicua :: Integer -> Bool\n<\/pre>\n
tal que esCapicua x<\/code> se verifica si x<\/code> es capic\u00faa. Por ejemplo,<\/p>\n
\n   esCapicua 252  ==  True\n   esCapicua 253  ==  False\n<\/pre>\n
Ejercicio 2.<\/strong> Definir la funci\u00f3n<\/p>\n
\n   inverso :: Integer -> Integer\n<\/pre>\n
tal que inverso x<\/code> es el n\u00famero obtenido escribiendo las cifras de x<\/code> en orden inverso. Por ejemplo,<\/p>\n
\n   inverso 253  ==  352\n<\/pre>\n
Ejercicio 3.<\/strong> Definir la funci\u00f3n<\/p>\n
\n   siguiente :: Integer -> Integer\n<\/pre>\n
tal que siguiente x<\/code> es el n\u00famero obtenido sum\u00e1ndole a x<\/code> su inverso. Por ejemplo,<\/p>\n
\n   siguiente 253  ==  605\n<\/pre>\n
Ejercicio 4.<\/strong> Definir la funci\u00f3n<\/p>\n
\n   busquedaDeCapicua :: Integer -> [Integer]\n<\/pre>\n
tal que busquedaDeCapicua x<\/code> es la lista de los n\u00fameros tal que el primero es x<\/code>, el segundo es el siguiente de x<\/code> y as\u00ed sucesivamente hasta que se alcanza un capic\u00faa. Por ejemplo,<\/p>\n
\n   busquedaDeCapicua 253  ==  [253,605,1111]\n<\/pre>\n
Ejercicio 5.<\/strong> Definir la funci\u00f3n<\/p>\n
\n   capicuaFinal :: Integer -> Integer\n<\/pre>\n
tal que capicuaFinal x<\/code> es la capic\u00faa con la que termina la b\u00fasqueda de capic\u00faa a partir de x<\/code>. Por ejemplo,<\/p>\n
\n   capicuaFinal 253  ==  1111\n<\/pre>\n
Ejercicio 6.<\/strong> Definir la funci\u00f3n<\/p>\n
\n   orden :: Integer -> Integer\n<\/pre>\n
tal que orden x<\/code> es el n\u00famero de veces que se repite el proceso de calcular el inverso a partir de x<\/code> hasta alcanzar un n\u00famero capic\u00faa. Por ejemplo,<\/p>\n
\n   orden 253  ==  2\n<\/pre>\n
Ejercicio 7.<\/strong> Definir la funci\u00f3n<\/p>\n
\n   ordenMayor :: Integer -> Integer -> Bool\n<\/pre>\n
tal que ordenMayor x n<\/code> se verifica si el orden de x<\/code> es mayor o igual que n<\/code>. Dar la definici\u00f3n sin necesidad de evaluar el orden de x<\/code>. Por ejemplo,<\/p>\n
\n   \u03bb> ordenMayor 1186060307891929990 2\n   True\n   \u03bb> orden 1186060307891929990\n   261\n<\/pre>\n
Ejercicio 8.<\/strong> Definir la funci\u00f3n<\/p>\n
\n   ordenEntre :: Integer -> Integer -> [Integer]\n<\/pre>\n
tal que ordenEntre m n<\/code> es la lista de los elementos cuyo orden esmayor o igual que m<\/code> y menor que n<\/code>. Por ejemplo,<\/p>\n
\n   take 5 (ordenEntre 10 11)  ==  [829,928,9059,9149,9239]\n<\/pre>\n
Ejercicio 9.<\/strong> Definir la funci\u00f3n<\/p>\n
\n   menorDeOrdenMayor :: Integer -> Integer\n<\/pre>\n
tal que menorDeOrdenMayor n<\/code> es el menor elemento cuyo orden es mayor que n<\/code>. Por ejemplo,<\/p>\n
\n   menorDeOrdenMayor 2   ==  19\n   menorDeOrdenMayor 20  ==  89\n<\/pre>\n
Ejercicio 10.<\/strong> Definir la funci\u00f3n<\/p>\n
\n   menoresdDeOrdenMayor :: Integer -> [(Integer,Integer)]\n<\/pre>\n
tal que menoresdDeOrdenMayor m<\/code> es la lista de los pares (n,x)<\/code> tales que n<\/code> es un n\u00famero entre 1 y m<\/code> y x<\/code> es el menor elemento de orden mayor que n<\/code>. Por ejemplo,<\/p>\n
\n   menoresdDeOrdenMayor 5  ==  [(1,10),(2,19),(3,59),(4,69),(5,79)]\n<\/pre>\n
Ejercicio 11.<\/strong> A la vista de los resultados de menoresdDeOrdenMayor 5<\/code> conjeturar sobre la \u00faltima cifra de menorDeOrdenMayor<\/code>.<\/p>\n
Ejercicio 12.<\/strong> Decidir con QuickCheck la conjetura.<\/p>\n
Ejercicio 13.<\/strong> Calcular menoresdDeOrdenMayor 50<\/code><\/p>\n
Ejercicio 14.<\/strong> A la vista de menoresdDeOrdenMayor 50<\/code>, conjeturar el orden de 196.<\/p>\n
Ejercicio 15.<\/strong> Comprobar con QuickCheck la conjetura sobre el orden de 196.<\/p>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\nimport Test.QuickCheck\n\n-- Soluci\u00f3n de ejercicio 1\nesCapicua :: Integer -> Bool\nesCapicua x = x' == reverse x'\n  where x' = show x\n\n-- Soluci\u00f3n de ejercicio 2\ninverso :: Integer -> Integer\ninverso = read . reverse . show\n\n-- Soluci\u00f3n de ejercicio 3\nsiguiente :: Integer -> Integer\nsiguiente x = x + inverso x\n\n-- Soluci\u00f3n de ejercicio 4\nbusquedaDeCapicua :: Integer -> [Integer]\nbusquedaDeCapicua x | esCapicua x = [x]\n                    | otherwise   = x : busquedaDeCapicua (siguiente x)\n\n-- Soluci\u00f3n de ejercicio 5\ncapicuaFinal :: Integer -> Integer\ncapicuaFinal x = last (busquedaDeCapicua x)\n\n-- Soluci\u00f3n de ejercicio 6\norden :: Integer -> Integer\norden x | esCapicua x = 0\n        | otherwise   = 1 + orden (siguiente x)\n\n-- Soluci\u00f3n de ejercicio 7\nordenMayor :: Integer -> Integer -> Bool\nordenMayor x n | esCapicua x = n == 0\n               | n <= 0      = True\n               | otherwise   = ordenMayor (siguiente x) (n-1)\n\n-- Soluci\u00f3n de ejercicio 8\nordenEntre :: Integer -> Integer -> [Integer]\nordenEntre m n = [x | x <- [1..], ordenMayor x m, not (ordenMayor x n)]\n\n-- Soluci\u00f3n de ejercicio 9\nmenorDeOrdenMayor :: Integer -> Integer\nmenorDeOrdenMayor n = head [x | x <- [1..], ordenMayor x n]\n\n-- Soluci\u00f3n de ejercicio 10\nmenoresdDeOrdenMayor :: Integer -> [(Integer,Integer)]\nmenoresdDeOrdenMayor m = [(n,menorDeOrdenMayor n) | n <- [1..m]]\n\n-- Soluci\u00f3n de ejercicio 11\n-- La conjetura es que para n mayor que 1, la \u00faltima cifra de\n-- (menorDeOrdenMayor n) es 9.\n\n-- Soluci\u00f3n de ejercicio 12\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--    \u03bb> 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--    \u03bb> menorDeOrdenMayor 25\n--    196\n\n-- Soluci\u00f3n de ejercicio 13\n-- El c\u00e1lculo es\n--    \u03bb> 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-- Soluci\u00f3n de ejercicio 14\n-- La conjetura es que el orden de 196 es infinito y, por tanto,\n-- 196 es un n\u00famero del Lychrel.\n\n-- Soluci\u00f3n de ejercicio 15\n-- ========================\n\n-- La propiedad es\nprop_ordenDe196 :: Integer -> Bool\nprop_ordenDe196 n =\n  ordenMayor 196 n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_ordenDe196\n--    +++ OK, passed 100 tests.\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom itertools import islice\nfrom sys import setrecursionlimit\nfrom typing import Generator, Iterator\n\nfrom hypothesis import given, settings\nfrom hypothesis import strategies as st\n\nsetrecursionlimit(10**6)\n\n# Soluci\u00f3n del ejercicio 1\ndef esCapicua(x: int) -> bool:\n    return x == int(str(x)[::-1])\n\n# Soluci\u00f3n del ejercicio 2\ndef inverso(x: int) -> int:\n    return int(str(x)[::-1])\n\n# Soluci\u00f3n del ejercicio 3\ndef siguiente(x: int) -> int:\n    return x + inverso(x)\n\n# Soluci\u00f3n del ejercicio 4\ndef busquedaDeCapicua(x: int) -> list[int]:\n    if esCapicua(x):\n        return [x]\n    return [x] + busquedaDeCapicua(siguiente(x))\n\n# Soluci\u00f3n del ejercicio 5\ndef capicuaFinal(x: int) -> int:\n    return busquedaDeCapicua(x)[-1]\n\n# Soluci\u00f3n del ejercicio 6\ndef orden(x: int) -> int:\n    if esCapicua(x):\n        return 0\n    return 1 + orden(siguiente(x))\n\n# Soluci\u00f3n del ejercicio 7\ndef ordenMayor(x: int, n: int) -> bool:\n    if esCapicua(x):\n        return n == 0\n    if n <= 0:\n        return True\n    return ordenMayor(siguiente(x), n - 1)\n\n# Soluci\u00f3n del ejercicio 8\n# ========================\n\n# naturales es el generador de los n\u00fameros naturales positivos, Por\n# ejemplo,\n#    >>> list(islice(naturales(), 5))\n#    [1, 2, 3, 4, 5]\ndef naturales() -> Iterator[int]:\n    i = 1\n    while True:\n        yield i\n        i += 1\n\ndef ordenEntre(m: int, n: int) -> Generator[int, None, None]:\n    return (x for x in naturales()\n            if ordenMayor(x, m) and not ordenMayor(x, n))\n\n# Soluci\u00f3n del ejercicio 9\ndef menorDeOrdenMayor(n: int) -> int:\n    return list(islice((x for x in naturales() if ordenMayor(x, n)), 1))[0]\n\n# Soluci\u00f3n del ejercicio 10\ndef menoresdDeOrdenMayor(m: int) -> list[tuple[int, int]]:\n    return [(n, menorDeOrdenMayor(n)) for n in range(1, m + 1)]\n\n# Soluci\u00f3n del ejercicio 11\n# La conjetura es que para n mayor que 1, la \u00faltima cifra de\n# menorDeOrdenMayor(n) es 9.\n\n# Soluci\u00f3n del ejercicio 12\n# =========================\n\n# La conjetura es\n# @given(st.integers(min_value=2, max_value=200))\n# def test_menorDeOrdenMayor(n: int) -> None:\n#     assert menorDeOrdenMayor(n) % 10 == 9\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q numeros_de_Lychrel.py\n#    E       assert (196 % 10) == 9\n#    E        +  where 196 = menorDeOrdenMayor(25)\n#    E       Falsifying example: test_menorDeOrdenMayor(\n#    E           n=25,\n#    E       )\n\n# Se puede comprobar que 25 es un contraejemplo,\n#    >>> menorDeOrdenMayor(25)\n#    196\n\n# Soluci\u00f3n del ejercicio 13\n# El c\u00e1lculo es\n#    \u03bb> 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# Soluci\u00f3n del ejercicio 14\n# El orden de 196 es infinito y, por tanto, 196 es un n\u00famero\n# de Lychrel.\n\n\n# Soluci\u00f3n del ejercicio 15\n# =========================\n\n# La propiedad es\n@settings(deadline=None)\n@given(st.integers(min_value=2, max_value=5000))\ndef test_ordenDe196(n: int) -> None:\n    assert ordenMayor(196, n)\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q numeros_de_Lychrel.py\n#    1 passed in 7.74s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Un n\u00famero de Lychrel es un n\u00famero 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 en dos…<\/p>\n","protected":false},"author":1,"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":[581],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7500"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=7500"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7500\/revisions"}],"predecessor-version":[{"id":7654,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7500\/revisions\/7654"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7500"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7500"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7500"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}