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
|
1 |
esCapicua :: Integer -> Bool |
tal que esCapicua x se verifica si x es capicúa. Por ejemplo,
|
1 2 |
esCapicua 252 == True esCapicua 253 == False |
Ejercicio 2. Definir la función
|
1 |
inverso :: Integer -> Integer |
tal que inverso x es el número obtenido escribiendo las cifras de x en orden inverso. Por ejemplo,
|
1 |
inverso 253 == 352 |
Ejercicio 3. Definir la función
|
1 |
siguiente :: Integer -> Integer |
tal que siguiente x es el número obtenido sumándole a x su inverso. Por ejemplo,
|
1 |
siguiente 253 == 605 |
Ejercicio 4. Definir la función
|
1 |
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,
|
1 |
busquedaDeCapicua 253 == [253,605,1111] |
Ejercicio 5. Definir la función
|
1 |
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,
|
1 |
capicuaFinal 253 == 1111 |
Ejercicio 6. Definir la función
|
1 |
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,
|
1 |
orden 253 == 2 |
Ejercicio 7. Definir la función
|
1 |
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,
|
1 2 3 4 |
λ> ordenMayor 1186060307891929990 2 True λ> orden 1186060307891929990 261 |
Ejercicio 8. Definir la función
|
1 |
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,
|
1 |
take 5 (ordenEntre 10 11) == [829,928,9059,9149,9239] |
Ejercicio 9. Definir la función
|
1 |
menorDeOrdenMayor :: Integer -> Integer |
tal que menorDeOrdenMayor n es el menor elemento cuyo orden es mayor que n. Por ejemplo,
|
1 2 |
menorDeOrdenMayor 2 == 19 menorDeOrdenMayor 20 == 89 |
Ejercicio 10. Definir la función
|
1 |
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,
|
1 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
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. |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
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 |