Problema 196

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 24 de octubre de 2019; las comprobaciones requieren 44 ediciones .

El problema del número 196 es el nombre condicional de un problema matemático sin resolver : no se sabe si la operación de “voltear y sumar” aplicada al número 196 un determinado número de veces conducirá a un palíndromo .

Un número de Lychrel es un número natural que no puede convertirse en un palíndromo mediante un proceso iterativo de "voltear y sumar" en notación decimal. Este proceso se llama el algoritmo 196 . El nombre Lychrel, acuñado por Wade VanLandingham , es un anagrama inexacto del nombre de su novia , Cheryl . No hay números de Lichrel rigurosamente probados (para el sistema numérico decimal; hay números de Lichrel probados para algunos otros sistemas numéricos), pero se supone que muchos números lo son, siendo el más pequeño 196 .

Voltear y doblar

La operación “ Reverse-and-add ” consiste en sumar el número original con su copia “invertida”, es decir, un número cuyos dígitos se escriben en orden inverso. Por ejemplo, 56 + 65 = 121, 521 + 125 = 646.

Esta operación se puede aplicar a cualquier número natural. Si como resultado de aplicar esta operación N veces a un determinado número se obtiene un palíndromo , entonces dicho número se denomina "palíndromo diferido" , resuelto en N iteraciones. A diferencia de los palíndromos diferidos, para los números de Lishrel esta operación no da como resultado un palíndromo, por muchas veces que la realicemos.

Algunos números (en particular, todos los números de un dígito y casi todos los números de dos dígitos) se convierten en palíndromos con bastante rapidez, después de aplicar solo unas pocas operaciones. Entonces, alrededor del 80% de todos los números menores de 10,000 se resuelven en un palíndromo en 4 o menos iteraciones. Alrededor del 91% - en 7 o menos iteraciones. Y solo dos números, 89 y 98, requieren una cantidad inusualmente grande: 24 operaciones.

Estos son algunos ejemplos de palíndromos tardíos:

56 se convierte en un palíndromo después de una iteración: 56 + 65 = 121 .
57 se convierte en un palíndromo después de dos iteraciones: 57 + 75 = 132, 132 + 231 = 363 .
59 se convierte en un palíndromo después de tres iteraciones: 59 + 95 = 154, 154 + 451 = 605, 605 + 506 = 1111 .
89 requiere 24 iteraciones inusualmente largas antes de llegar al palíndromo 8813200023188 (este es el mayor número de operaciones entre números hasta 10000 que la comunidad científica actualmente sabe con certeza que se resuelven en un palíndromo).
10,911 alcanza el palíndromo 4668731596684224866951378664 después de 55 iteraciones .

El número más pequeño, comenzando con 1 , que aparentemente no forma un palíndromo es el número de tres dígitos 196 . Este es el número decimal potencial de Lichrel más pequeño conocido.

Palíndromos más tardíos

Entre la infinidad de palíndromos retrasados, resultan especialmente interesantes aquellos números que requieren mayor número de iteraciones para convertirse en palíndromos.

Так, 30 ноября 2005 года Джейсоном Дусеттом ( англ. Jason Doucette ) с помощью компьютера был найден отложенный палиндром 1 186 060 307 891 929 990 , который после 261 итерации становится 119- значным палиндромом 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 . Este número ostentaba el récord mundial de palíndromos más retrasados durante más de 13 años.

En mayo de 2017, el canal de televisión MIR24 informó que el escolar moscovita Andrey Shchebetov había descubierto el palíndromo tardío más grande conocido, el número 1999291987030606810 . Sin embargo, este número no tiene nada de interesante, ya que se obtiene mediante una simple permutación de pares de dígitos simétricos a partir del número descubierto por Jason Doucette. El mayor número conocido de 19 dígitos que se resuelve en 261 iteraciones es 1,999,999,936,042,548,910 , y el mayor número conocido tiene 35 dígitos .

El 26 de abril de 2019, Rob van Nobelen (holandés . Rob van Nobelen ) estableció un nuevo récord mundial de palíndromos más retrasados: el número de 23 dígitos 12.000.700.000.025.339.936.491 , que se convierte en palíndromo en 288 pasos.

El 5 de enero de 2021, Anton Stefanov publicó [1] los números de 23 dígitos 13,968,441,660,506,503,386,020 y 13,568,441,660,506,503,386,420 , que se convierten en el mismo palíndromo en 289 pasos que el número encontrado por Rob van Nobelen estableciendo un nuevo récord. El 14 de octubre de 2021, Dmitry Maslov informó [2] que encontró un número más pequeño de 23 dígitos que se resuelve en 289 iteraciones: 10 036 069 400 174 999 499 950 .

El 14 de diciembre de 2021, Dmitry Maslov estableció [3] un nuevo récord mundial entre los palíndromos más retrasados: el número de 25 dígitos 1000206827388999999095750 , que después de 293 iteraciones se convierte en un palíndromo de 132 dígitos. Este número es el récord mundial actual de palíndromos más retrasados.

La secuencia OEIS A326414 contiene 19353600 números que se convierten en un palíndromo después de 288 pasos.

La secuencia A281506 contiene una lista de 108864 palíndromos retrasados, que requieren 261 iteraciones para convertirse en un palíndromo. Comienza con 1186060307891929990 y termina con 1999291987030606810 .

Explicación de la fórmula

Digamos que es un número natural. Definimos la función Lichrel para números base (ver definiciones relacionadas) de la siguiente manera: ${\mathcal {n))$ ${\textstyle b>1\ F_{b}:\mathbb {N} \rightarrow \mathbb {N} }$

$F_{b}(n)=n\ +\sum _{i=0}^{k-1}d_{i}b^{ki-1}$

donde es el número de dígitos en el número base , y $k=\lpiso \log _{b}n\rpiso +1$ $b$

$d_{i}={\frac {n{\bmod {b}}^{i+1}-n{\bmod {b}}^{i}}{b^{i}}}$

el valor de cada dígito del número. Un número es un número de Lichrel si no existe un número natural tal que , donde es iteraciones $i$ $F_{b}^{i+1}(n)=2F_{b}^{i}(n)$ $F ^ yo$ $i$ $F$

Nuevo problema

En otros sistemas numéricos , se puede demostrar que algunos números nunca forman un palíndromo después de iteraciones sucesivas [4] [5] , pero no se ha encontrado tal evidencia para 196 y otros números decimales.

Existe la conjetura de que 196 y otros números que aún no se han convertido en palíndromos son números de Lishrel, pero no hay pruebas rigurosas de que lo sean. Dichos números se denominan informalmente "candidatos para los números de Lichrel". Los primeros candidatos para los números de Lychrel son la secuencia A023108 en el OEIS :

196 295 394 493 592 689 691 788 790 879 887 978 986 1495 1497 1585 1587 1675 1677 1765 1767 185,5 1845,7 1997 _

Los que están en negrita se consideran números básicos de Lychrel (ver más abajo ). Los programas de computadora de Jason Doucette, Jan Peters y Benjamin Despres encontraron otros candidatos para Lishrel. Además, Benjamin Despres identificó todos los números base de Lichrel con menos de 17 dígitos [6] . El sitio de Wade VanLandingham contiene listas de números base de Lychrel para cada longitud de número. [7]

El método de fuerza bruta , desarrollado originalmente por John Walker, se ha mejorado para aprovechar el comportamiento de iteración. Por ejemplo, hay un programa creado por Won Suite que guarda solo los primeros y últimos dígitos de cada iteración, lo que le permite probar patrones digitales en millones de iteraciones sin tener que guardar cada iteración en un archivo [8] . Pero hasta ahora no se ha inventado ningún algoritmo que eluda el proceso iterativo.

Definiciones relacionadas

El término hilo o thread ( en inglés thread ) fue inventado por Jason Doucette, denotando la secuencia de números obtenidos como resultado de iteraciones del número original. El número base ( ing. seed ) y sus números relacionados relacionados ( ing. kin ) convergen en una secuencia. La secuencia no incluye el número base original o su relativo , sino solo los números que son comunes a ambos, después de que convergen.

Los números base son una subsecuencia de los números de Lichrel, es decir, el número más pequeño de cada flujo que no produce un palíndromo. El número base puede ser en sí mismo un palíndromo. Los primeros tres ejemplos están en negrita en la lista anterior.

Los números relacionados son un subconjunto de los números de Lichrel que incluyen todos los números de la secuencia excepto el base, o cualquier número que se una a la secuencia dada después de una iteración. El término fue introducido por Koji Yamashita en 1997.

Relé número 196

Dado que el número 196 es el candidato más pequeño para los números de Lichrel, ha recibido la mayor atención.

John Walker inició el relevo 196 el 12 de agosto de 1987 en la estación de trabajo Sun 3/260. Escribió un programa en C que itera "voltear y agregar" y busca un palíndromo después de cada paso. El programa se estaba ejecutando en segundo plano con una prioridad baja. Volcó los resultados de la iteración en un archivo cada dos horas y en el momento del apagado del sistema, registrando el número y el número de iteraciones alcanzado en ese momento. Se reiniciaba automáticamente desde el último punto de control cada vez que se encendía la computadora. Funcionó durante casi tres años y luego se detuvo (como estaba programado) el 24 de mayo de 1990 con el mensaje:

Se ha alcanzado el punto de parada en el paso 2 415 836. El número contiene 1.000.000 dígitos. Texto original (inglés)[ mostrarocultar] Punto de parada alcanzado en el paso 2.415.836.
El número contiene 1,000,000 dígitos.

196 aumentó a un millón de dígitos después de 2.415.836 iteraciones sin llegar a un palíndromo. Walker publicó sus hallazgos en línea junto con el último punto de control, invitando a otros a reanudar su búsqueda en función del último número alcanzado.

En 1995, Tim Irwin utilizó la supercomputadora de aquellos años, alcanzando la marca de los dos millones de dígitos en tan solo tres meses, nuevamente sin encontrar palíndromo. Jason Doucette luego se unió a esta dirección cuantitativa y alcanzó 12,5 millones de cifras en mayo de 2000. Wade VanLandingham, utilizando el programa de Jason Doucette, alcanzó los 13 millones de dígitos, que se publicaron [9] en Yes Mag , una revista científica canadiense para niños. Desde junio de 2000, Wade VanLendingham ha continuado llevando la bandera, usando programas escritos por varios entusiastas. El 1 de mayo de 2006, VanLendingham alcanzó la marca de los 300 millones de dígitos (a razón de un millón de dígitos cada 5 a 7 días). Usando computación distribuida , en 2011 Romain Dolbeau ( fr. Romain Dolbeau ) hizo mil millones de iteraciones y obtuvo un número que consta de 413,930,770 dígitos [10] , en julio de 2012 sus cálculos alcanzaron un número con 600 millones de dígitos, y en febrero de 2015 el número dígitos superó los mil millones [11] , pero el palíndromo nunca fue descubierto.

Otros candidatos de Lishrel que se han sometido a la misma búsqueda incluyen 879, 1997, 7059 y otros números base: se han rastreado durante millones y decenas de millones de iteraciones sin encontrar un palíndromo [12] [13] .

Notas

↑ Antón Stefanov (stefanov94). Posponer palíndromos para el nuevo año (ruso) // Habr: sitio. - 2021. - 5 de enero. Archivado desde el original el 7 de enero de 2021.
↑ Dmitri Maslov. Se encontró el palíndromo retrasado más pequeño para el paso 289 (ruso) // proyecto iLWN: sitio. - 2021. - 14 de octubre. Archivado desde el original el 6 de noviembre de 2021.
↑ Dmitri Maslov. Se ha establecido un nuevo récord mundial de palíndromos retrasados: ¡293 iteraciones! (Ruso) // iLWN: sitio. - 2021. - 14 de diciembre. Archivado desde el original el 6 de noviembre de 2021.
↑ Copia archivada . Consultado el 29 de mayo de 2006. Archivado desde el original el 16 de mayo de 2006. (indefinido)
↑ Sumas de inversión de dígitos que conducen a palíndromos (enlace no disponible) . Fecha de acceso: 4 de enero de 2011. Archivado desde el original el 6 de febrero de 2010. (indefinido)
↑ Copia archivada (enlace no disponible) . Consultado el 4 de enero de 2011. Archivado desde el original el 18 de marzo de 2010. (indefinido)
↑ Copia archivada (enlace no disponible) . Fecha de acceso: 4 de enero de 2011. Archivado desde el original el 26 de julio de 2010. (indefinido)
↑ Copia archivada . Consultado el 15 de octubre de 2006. Archivado desde el original el 15 de octubre de 2006. (indefinido)
↑ ¿Ir o venir? (Inglés)
↑ La implementación p196_mpi del algoritmo Reverse-And-Add para Palindrome Quest . Fecha de acceso: 17 de enero de 2015. Archivado desde el original el 19 de abril de 2015. (indefinido)
↑ La página p196_mpi . Fecha de acceso: 17 de enero de 2015. Archivado desde el original el 11 de febrero de 2015. (indefinido)
↑ Registros de Lychrel . Archivado desde el original el 21 de octubre de 2006. (indefinido)
↑ Encontrar el proyecto Palindrome 196-iLWN . Consultado el 6 de noviembre de 2021. Archivado desde el original el 6 de noviembre de 2021. (indefinido)

Enlaces

John Walker (inglés) - tres años de informática.
Tim Irwin (inglés) : unos dos meses de informática.
Jason Doucette - World Records (inglés) - "Relevo del número 196", los palíndromos más retrasados.
Benjamín Despres (inglés) .
196 y otros números de Lichrel. Sitio web de Wade Van Landingham .
Weisstein, Eric W. 196-Algorithm (inglés) en el sitio web de Wolfram MathWorld .
Weisstein, Eric W. Lychrel Número (inglés) en el sitio web Wolfram MathWorld .
Weisstein, Eric W. Palindromic Number Conjecture (inglés) en el sitio web de Wolfram MathWorld .
Weisstein, Eric W. Reverse-Then-Add Sequence (inglés) en el sitio web de Wolfram MathWorld .
MathPages: suma de dígitos que da como resultado palíndromos
Historias sobre matemáticos. Clara Ziskin. Mención del problema en la literatura en lengua rusa.
Todos los palíndromos retrasados conocidos son de Dmitry Maslov, proyecto MDPN.
Control de palíndromo retrasado : Dmitry Maslov, proyecto MDPN.