Un número de Lychrel es un número natural que no puede formar un palíndromo mediante el proceso iterativo de invertir repetidamente sus dígitos y sumar los números resultantes. Este proceso a veces se denomina algoritmo 196 , en honor al número más famoso asociado con el proceso. En base diez , todavía no se ha demostrado que existan números de Lychrel, pero se sospecha que existen muchos, incluido el 196, por motivos heurísticos [1] y estadísticos . El nombre "Lychrel" fue acuñado por Wade Van Landingham como un anagrama aproximado de "Cheryl", el primer nombre de su novia. [2]
El proceso de invertir y sumar produce la suma de un número y el número formado al invertir el orden de sus dígitos. Por ejemplo, 56 + 65 = 121. Otro ejemplo: 125 + 521 = 646.
Algunos números se convierten rápidamente en palíndromos después de repetidas inversiones y sumas, y por lo tanto no son números de Lychrel. Todos los números de uno y dos dígitos se convierten eventualmente en palíndromos después de repetidas inversiones y sumas.
Aproximadamente el 80% de todos los números menores de 10.000 se resuelven en un palíndromo en cuatro pasos o menos; aproximadamente el 90% de ellos se resuelven en siete pasos o menos. A continuación, se muestran algunos ejemplos de números que no son de Lychrel:
El número más pequeño que no se conoce que forme un palíndromo es 196. Por lo tanto, es el candidato a número de Lychrel más pequeño.
El número resultante de la inversión de los dígitos de un número Lychrel que no termina en cero también es un número Lychrel.
Sea un número natural. Definimos la función de Lychrel para un número base b > 1, como sigue:
¿Dónde está el número de dígitos del número en base , y
es el valor de cada dígito del número. Un número es un número de Lychrel si no existe un número natural tal que , donde es la iteración -ésima de
En otras bases (estas bases son potencias de 2 , como el binario y el hexadecimal ), se puede demostrar que ciertos números nunca forman un palíndromo después de repetidas inversiones y sumas, [3] pero no se ha encontrado tal prueba para 196 y otros números de base 10.
Se conjetura que 196 y otros números que aún no han dado lugar a un palíndromo son números de Lychrel, pero todavía no se ha demostrado que ningún número en base diez sea de Lychrel. Los números que no se ha demostrado que no sean de Lychrel se denominan informalmente números "candidatos de Lychrel". Los primeros números candidatos de Lychrel (secuencia A023108 en la OEIS ) son:
Los números en negrita son números de semillas de Lychrel sospechosos (ver abajo). Los programas de computadora de Jason Doucette, Ian Peters y Benjamin Despres han encontrado otros candidatos de Lychrel. De hecho, el programa de Benjamin Despres ha identificado todos los números de semillas de Lychrel sospechosos de menos de 17 dígitos. [4] El sitio de Wade Van Landingham enumera el número total de números de semillas de Lychrel sospechosos encontrados para cada longitud de dígito. [5]
El método de fuerza bruta implementado originalmente por John Walker se ha perfeccionado para aprovechar los comportamientos de iteración. Por ejemplo, Vaughn Suite ideó un programa que solo guarda los primeros y los últimos dígitos de cada iteración, lo que permite realizar pruebas de los patrones de dígitos en millones de iteraciones sin tener que guardar cada iteración completa en un archivo. [6] Sin embargo, hasta ahora no se ha desarrollado ningún algoritmo para evitar el proceso iterativo de inversión y adición.
El término hilo , acuñado por Jason Doucette, se refiere a la secuencia de números que pueden o no conducir a un palíndromo a través del proceso de inversión y suma. Cualquier semilla dada y sus números de parentesco asociados convergerán en el mismo hilo. El hilo no incluye la semilla original ni el número de parentesco , sino solo los números que son comunes a ambos, después de que convergen.
Los números de semilla son un subconjunto de los números de Lychrel, es decir, el número más pequeño de cada hilo que no produce palíndromos. Un número de semilla puede ser un palíndromo en sí mismo. Los primeros tres ejemplos se muestran en negrita en la lista anterior.
Los números de Kin son un subconjunto de los números de Lychrel, que incluyen todos los números de un hilo, excepto la semilla, o cualquier número que converja en un hilo determinado después de una única iteración. Este término fue introducido por Koji Yamashita en 1997.
Debido a que 196 ( base 10 ) es el número de Lychrel candidato más pequeño, ha recibido la mayor atención.
En la década de 1980, el problema del palíndromo 196 atrajo la atención de los aficionados a las microcomputadoras , y los programas de búsqueda de Jim Butterfield y otros aparecieron en varias revistas de informática de mercado masivo. [7] [8] [9] En 1985, un programa de James Killman se ejecutó sin éxito durante más de 28 días, repitiendo 12.954 pases y alcanzando un número de 5366 dígitos. [9]
John Walker comenzó su misión 196 Palindrome Quest el 12 de agosto de 1987 en una estación de trabajo Sun 3/260. Escribió un programa en C para realizar las iteraciones de inversión y adición y para comprobar si había un palíndromo después de cada paso. El programa se ejecutaba en segundo plano con una prioridad baja y generaba un punto de control en un archivo cada dos horas y cuando se apagaba el sistema, registrando el número alcanzado hasta el momento y el número de iteraciones. Se reiniciaba automáticamente desde el último punto de control después de cada apagado. Se ejecutó durante casi tres años y luego finalizó (según las instrucciones) el 24 de mayo de 1990 con el mensaje:
El número 196 había crecido hasta alcanzar un millón de dígitos después de 2.415.836 iteraciones sin llegar a un palíndromo. Walker publicó sus hallazgos en Internet junto con el último punto de control, invitando a otros a reanudar la búsqueda utilizando el número alcanzado hasta el momento.
En 1995, Tim Irvin y Larry Simkins utilizaron una computadora multiprocesador y alcanzaron la marca de los dos millones de dígitos en solo tres meses sin encontrar un palíndromo. Jason Doucette siguió su ejemplo y alcanzó los 12,5 millones de dígitos en mayo de 2000. Wade VanLandingham utilizó el programa de Jason Doucette para alcanzar los 13 millones de dígitos, un récord publicado en Yes Mag: la revista científica infantil de Canadá. Desde junio de 2000, Wade VanLandingham ha llevado la bandera utilizando programas escritos por varios entusiastas. Para el 1 de mayo de 2006, VanLandingham había alcanzado la marca de los 300 millones de dígitos (a un ritmo de un millón de dígitos cada 5 a 7 días). Utilizando el procesamiento distribuido , [10] en 2011 Romain Dolbeau completó mil millones de iteraciones para producir un número con 413.930.770 dígitos, y en febrero de 2015 sus cálculos alcanzaron un número con mil millones de dígitos. [11] Aún no se ha encontrado ningún palíndromo.
Otros números de Lychrel potenciales que también han sido sometidos al mismo método de fuerza bruta de adición inversa repetida incluyen 879, 1997 y 7059: se han llevado a varios millones de iteraciones sin que se haya encontrado ningún palíndromo. [12]
En base 2 , se ha demostrado que 10110 (22 en decimal) es un número de Lychrel, ya que después de 4 pasos llega a 10110100, después de 8 pasos llega a 1011101000, después de 12 pasos llega a 101111010000, y en general después de 4 n pasos llega a un número que consta de 10, seguido de n + 1 unos, seguido de 01, seguido de n + 1 ceros. Este número obviamente no puede ser un palíndromo, y ninguno de los otros números de la secuencia son palíndromos.
Se ha demostrado que los números de Lychrel existen en las siguientes bases: 11, 17, 20, 26 y todas las potencias de 2. [13] [14] [15]
Ninguna base contiene números de Lychrel menores que la base. De hecho, en cualquier base b dada , ningún número de un solo dígito requiere más de dos iteraciones para formar un palíndromo. Para b > 4, si k < b /2 entonces k se vuelve palindrómico después de una iteración: k + k = 2 k , que es un número de un solo dígito en la base b (y por lo tanto un palíndromo). Si k > b /2, k se vuelve palindrómico después de dos iteraciones.
Los números más pequeños en cada base que podrían ser un número de Lychrel son (secuencia A060382 en la OEIS ):
Los números de Lychrel se pueden extender a los números enteros negativos mediante el uso de una representación de dígitos con signo para representar cada número entero.
