Ir al contenido principal

Números de Lychrel

Un número de Lychrel es un número para el que nunca se obtiene un capicúa mediante el proceso de invertir las cifras y sumar los dos números. Por ejemplo, los siguientes números no son números de Lychrel: + 56, ya que en un paso se obtiene un capicúa: 56+65=121. + 57, ya que en dos pasos se obtiene un capicúa: 57+75=132, 132+231=363 + 59, ya que en dos pasos se obtiene un capicúa: 59+95=154, 154+451=605, 605+506=1111 + 89, ya que en 24 pasos se obtiene un capicúa. En esta serie de ejercicios vamos a buscar el primer número de Lychrel.

Ejercicio 1. Definir la función

   esCapicua :: Integer -> Bool

tal que esCapicua x se verifica si x es capicúa. Por ejemplo,

   esCapicua 252  ==  True
   esCapicua 253  ==  False

Ejercicio 2. Definir la función

   inverso :: Integer -> Integer

tal que inverso x es el número obtenido escribiendo las cifras de x en orden inverso. Por ejemplo,

   inverso 253  ==  352

Ejercicio 3. Definir la función

   siguiente :: Integer -> Integer

tal que siguiente x es el número obtenido sumándole a x su inverso. Por ejemplo,

   siguiente 253  ==  605

Ejercicio 4. Definir la función

   busquedaDeCapicua :: Integer -> [Integer]

tal que busquedaDeCapicua x es la lista de los números tal que el primero es x, el segundo es el siguiente de x y así sucesivamente hasta que se alcanza un capicúa. Por ejemplo,

   busquedaDeCapicua 253  ==  [253,605,1111]

Ejercicio 5. Definir la función

   capicuaFinal :: Integer -> Integer

tal que capicuaFinal x es la capicúa con la que termina la búsqueda de capicúa a partir de x. Por ejemplo,

   capicuaFinal 253  ==  1111

Ejercicio 6. Definir la función

   orden :: Integer -> Integer

tal que orden x es el número de veces que se repite el proceso de calcular el inverso a partir de x hasta alcanzar un número capicúa. Por ejemplo,

   orden 253  ==  2

Ejercicio 7. Definir la función

   ordenMayor :: Integer -> Integer -> Bool

tal que ordenMayor x n se verifica si el orden de x es mayor o igual que n. Dar la definición sin necesidad de evaluar el orden de x. Por ejemplo,

   λ> ordenMayor 1186060307891929990 2
   True
   λ> orden 1186060307891929990
   261

Ejercicio 8. Definir la función

   ordenEntre :: Integer -> Integer -> [Integer]

tal que ordenEntre m n es la lista de los elementos cuyo orden esmayor o igual que m y menor que n. Por ejemplo,

   take 5 (ordenEntre 10 11)  ==  [829,928,9059,9149,9239]

Ejercicio 9. Definir la función

   menorDeOrdenMayor :: Integer -> Integer

tal que menorDeOrdenMayor n es el menor elemento cuyo orden es mayor que n. Por ejemplo,

   menorDeOrdenMayor 2   ==  19
   menorDeOrdenMayor 20  ==  89

Ejercicio 10. Definir la función

   menoresdDeOrdenMayor :: Integer -> [(Integer,Integer)]

tal que menoresdDeOrdenMayor m es la lista de los pares (n,x) tales que n es un número entre 1 y m y x es el menor elemento de orden mayor que n. Por ejemplo,

   menoresdDeOrdenMayor 5  ==  [(1,10),(2,19),(3,59),(4,69),(5,79)]

Ejercicio 11. A la vista de los resultados de menoresdDeOrdenMayor 5 conjeturar sobre la última cifra de menorDeOrdenMayor.

Ejercicio 12. Decidir con QuickCheck la conjetura.

Ejercicio 13. Calcular menoresdDeOrdenMayor 50

Ejercicio 14. A la vista de menoresdDeOrdenMayor 50, conjeturar el orden de 196.

Ejercicio 15. Comprobar con QuickCheck la conjetura sobre el orden de 196.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Test.QuickCheck

-- Solución de ejercicio 1
esCapicua :: Integer -> Bool
esCapicua x = x' == reverse x'
  where x' = show x

-- Solución de ejercicio 2
inverso :: Integer -> Integer
inverso = read . reverse . show

-- Solución de ejercicio 3
siguiente :: Integer -> Integer
siguiente x = x + inverso x

-- Solución de ejercicio 4
busquedaDeCapicua :: Integer -> [Integer]
busquedaDeCapicua x | esCapicua x = [x]
                    | otherwise   = x : busquedaDeCapicua (siguiente x)

-- Solución de ejercicio 5
capicuaFinal :: Integer -> Integer
capicuaFinal x = last (busquedaDeCapicua x)

-- Solución de ejercicio 6
orden :: Integer -> Integer
orden x | esCapicua x = 0
        | otherwise   = 1 + orden (siguiente x)

-- Solución de ejercicio 7
ordenMayor :: Integer -> Integer -> Bool
ordenMayor x n | esCapicua x = n == 0
               | n <= 0      = True
               | otherwise   = ordenMayor (siguiente x) (n-1)

-- Solución de ejercicio 8
ordenEntre :: Integer -> Integer -> [Integer]
ordenEntre m n = [x | x <- [1..], ordenMayor x m, not (ordenMayor x n)]

-- Solución de ejercicio 9
menorDeOrdenMayor :: Integer -> Integer
menorDeOrdenMayor n = head [x | x <- [1..], ordenMayor x n]

-- Solución de ejercicio 10
menoresdDeOrdenMayor :: Integer -> [(Integer,Integer)]
menoresdDeOrdenMayor m = [(n,menorDeOrdenMayor n) | n <- [1..m]]

-- Solución de ejercicio 11
-- La conjetura es que para n mayor que 1, la última cifra de
-- (menorDeOrdenMayor n) es 9.

-- Solución de ejercicio 12
-- ========================

-- La conjetura es
prop_menorDeOrdenMayor :: Integer -> Property
prop_menorDeOrdenMayor n =
  n > 1 ==> menorDeOrdenMayor n `mod` 10 == 9

-- La comprobación es
--    λ> quickCheck prop_menorDeOrdenMayor
--    *** Failed! Falsifiable (after 22 tests and 2 shrinks):
--    25

-- Se puede comprobar que 25 es un contraejemplo,
--    λ> menorDeOrdenMayor 25
--    196

-- Solución de ejercicio 13
-- El cálculo es
--    λ> menoresdDeOrdenMayor 50
--    [(1,10),(2,19),(3,59),(4,69),(5,79),(6,79),(7,89),(8,89),(9,89),
--     (10,89),(11,89),(12,89),(13,89),(14,89),(15,89),(16,89),(17,89),
--     (18,89),(19,89),(20,89),(21,89),(22,89),(23,89),(24,89),(25,196),
--     (26,196),(27,196),(28,196),(29,196),(30,196),(31,196),(32,196),
--     (33,196),(34,196),(35,196),(36,196),(37,196),(38,196),(39,196),
--     (40,196),(41,196),(42,196),(43,196),(44,196),(45,196),(46,196),
--     (47,196),(48,196),(49,196),(50,196)]

-- Solución de ejercicio 14
-- La conjetura es que el orden de 196 es infinito y, por tanto,
-- 196 es un número del Lychrel.

-- Solución de ejercicio 15
-- ========================

-- La propiedad es
prop_ordenDe196 :: Integer -> Bool
prop_ordenDe196 n =
  ordenMayor 196 n

-- La comprobación es
--    λ> quickCheck prop_ordenDe196
--    +++ OK, passed 100 tests.

Soluciones en Python

from itertools import islice
from sys import setrecursionlimit
from typing import Generator, Iterator

from hypothesis import given, settings
from hypothesis import strategies as st

setrecursionlimit(10**6)

# Solución del ejercicio 1
def esCapicua(x: int) -> bool:
    return x == int(str(x)[::-1])

# Solución del ejercicio 2
def inverso(x: int) -> int:
    return int(str(x)[::-1])

# Solución del ejercicio 3
def siguiente(x: int) -> int:
    return x + inverso(x)

# Solución del ejercicio 4
def busquedaDeCapicua(x: int) -> list[int]:
    if esCapicua(x):
        return [x]
    return [x] + busquedaDeCapicua(siguiente(x))

# Solución del ejercicio 5
def capicuaFinal(x: int) -> int:
    return busquedaDeCapicua(x)[-1]

# Solución del ejercicio 6
def orden(x: int) -> int:
    if esCapicua(x):
        return 0
    return 1 + orden(siguiente(x))

# Solución del ejercicio 7
def ordenMayor(x: int, n: int) -> bool:
    if esCapicua(x):
        return n == 0
    if n <= 0:
        return True
    return ordenMayor(siguiente(x), n - 1)

# Solución del ejercicio 8
# ========================

# naturales es el generador de los números naturales positivos, Por
# ejemplo,
#    >>> list(islice(naturales(), 5))
#    [1, 2, 3, 4, 5]
def naturales() -> Iterator[int]:
    i = 1
    while True:
        yield i
        i += 1

def ordenEntre(m: int, n: int) -> Generator[int, None, None]:
    return (x for x in naturales()
            if ordenMayor(x, m) and not ordenMayor(x, n))

# Solución del ejercicio 9
def menorDeOrdenMayor(n: int) -> int:
    return list(islice((x for x in naturales() if ordenMayor(x, n)), 1))[0]

# Solución del ejercicio 10
def menoresdDeOrdenMayor(m: int) -> list[tuple[int, int]]:
    return [(n, menorDeOrdenMayor(n)) for n in range(1, m + 1)]

# Solución del ejercicio 11
# La conjetura es que para n mayor que 1, la última cifra de
# menorDeOrdenMayor(n) es 9.

# Solución del ejercicio 12
# =========================

# La conjetura es
# @given(st.integers(min_value=2, max_value=200))
# def test_menorDeOrdenMayor(n: int) -> None:
#     assert menorDeOrdenMayor(n) % 10 == 9

# La comprobación es
#    src> poetry run pytest -q numeros_de_Lychrel.py
#    E       assert (196 % 10) == 9
#    E        +  where 196 = menorDeOrdenMayor(25)
#    E       Falsifying example: test_menorDeOrdenMayor(
#    E           n=25,
#    E       )

# Se puede comprobar que 25 es un contraejemplo,
#    >>> menorDeOrdenMayor(25)
#    196

# Solución del ejercicio 13
# El cálculo es
#    λ> menoresdDeOrdenMayor 50
#    [(1,10),(2,19),(3,59),(4,69),(5,79),(6,79),(7,89),(8,89),(9,89),
#     (10,89),(11,89),(12,89),(13,89),(14,89),(15,89),(16,89),(17,89),
#     (18,89),(19,89),(20,89),(21,89),(22,89),(23,89),(24,89),(25,196),
#     (26,196),(27,196),(28,196),(29,196),(30,196),(31,196),(32,196),
#     (33,196),(34,196),(35,196),(36,196),(37,196),(38,196),(39,196),
#     (40,196),(41,196),(42,196),(43,196),(44,196),(45,196),(46,196),
#     (47,196),(48,196),(49,196),(50,196)]

# Solución del ejercicio 14
# El orden de 196 es infinito y, por tanto, 196 es un número
# de Lychrel.


# Solución del ejercicio 15
# =========================

# La propiedad es
@settings(deadline=None)
@given(st.integers(min_value=2, max_value=5000))
def test_ordenDe196(n: int) -> None:
    assert ordenMayor(196, n)

# La comprobación es
#    src> poetry run pytest -q numeros_de_Lychrel.py
#    1 passed in 7.74s