¿Existe algún número de Lychrel de base 10?
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 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 nombre de pila de su novia. [2]
El proceso de invertir y sumar produce la suma de un número y el número formado invirtiendo el orden de sus dígitos. Por ejemplo, 56 + 65 = 121. Como otro ejemplo, 125 + 521 = 646.
Algunos números se convierten en palíndromos rápidamente 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 eventualmente se convierten en palíndromos después de repetidas inversiones y sumas.
Alrededor del 80% de todos los números menores de 10.000 se resuelven en un palíndromo en cuatro o menos pasos; Alrededor del 90% de ellos se resuelven en siete pasos o menos. A continuación se muestran algunos ejemplos de números que no son Lychrel:
El número más pequeño que no se sabe que forme un palíndromo es 196 . Por tanto, es el candidato al número de Lychrel más pequeño.
El número resultante de la inversión de los dígitos de un número de Lychrel que no termina en cero también es un número de Lychrel.
Sea un número natural. Definimos la función Lychrel para una base numérica b > 1, , como la siguiente:
donde es 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 , ¿dónde está la -ésima iteración de
En otras bases (estas bases son potencias de 2 , como binaria y 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 producido un palíndromo son números de Lychrel, pero aún no se ha demostrado que ningún número en base diez sea Lychrel. Los números que no se ha demostrado que no sean Lychrel se denominan informalmente números "candidatos de Lychrel". Los primeros números candidatos de Lychrel (secuencia A023108 en OEIS ) son:
Los números en negrita son números de semillas sospechosas de Lychrel (ver más abajo). Los programas informáticos de Jason Doucette, Ian Peters y Benjamin Despres han encontrado otros candidatos a 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 sospechosas encontradas 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 ú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 eludir el proceso iterativo de inversión y suma.
El término hilo , acuñado por Jason Doucette, se refiere a la secuencia de números que pueden conducir o no a un palíndromo mediante el proceso inverso y de suma. Cualquier semilla dada y sus números de parentesco asociados convergerán en el mismo hilo. El hilo no incluye el número semilla o de parentesco original , sino sólo los números que son comunes a ambos, después de que convergen.
Los números de semillas 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 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 parentesco 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 convergerá en un hilo determinado después de una sola 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 programas de búsqueda de Jim Butterfield y otros aparecieron en varias revistas de informática del mercado masivo. [7] [8] [9] En 1985, un programa de James Killman se ejecutó sin éxito durante más de 28 días, realizando 12.954 pases y alcanzando un número de 5.366 dígitos. [9]
John Walker comenzó su 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 iteraciones de inversión y suma y para comprobar si había un palíndromo después de cada paso. El programa se ejecutaba en segundo plano con baja prioridad y producía un punto de control en un archivo cada dos horas y cuando se apagaba el sistema, registraba 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. Funcionó durante casi tres años y luego finalizó (según las instrucciones) el 24 de mayo de 1990 con el mensaje:
196 había crecido hasta 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 sólo tres meses sin encontrar un palíndromo. Jason Doucette luego hizo lo mismo y alcanzó 12,5 millones de dígitos en mayo de 2000. Wade VanLandingham utilizó el programa de Jason Doucette para alcanzar 13 millones de dígitos, un récord publicado en Yes Mag: la revista científica para niños de Canadá. Desde junio de 2000, Wade VanLandingham lleva la bandera utilizando programas escritos por varios entusiastas. 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 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 un palíndromo.
Otros posibles números de Lychrel que también han sido sometidos al mismo método de fuerza bruta de suma inversa repetida incluyen 879, 1997 y 7059: han sido llevados 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 un número que consta de 10, seguido de n + 1 unos, seguido de 01, seguido de n + 1 ceros. Obviamente, este número no puede ser un palíndromo y ninguno de los demás números de la secuencia es palíndromo.
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 más pequeños 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 de un solo dígito en base b (y por lo tanto un palíndromo). Si k > b /2, k se vuelve palindrómico después de dos iteraciones.
El número más pequeño en cada base que podría ser un número de Lychrel es (secuencia A060382 en OEIS ):
Los números de Lychrel se pueden extender a enteros negativos mediante el uso de una representación de dígitos con signo para representar cada número entero.
