¿Situación de la conjetura 196?

Question

Un palíndromo es un número que sigue siendo el mismo al invertirlo, por ejemplo 34143. Ahora escoge un número arbitrario, por ejemplo 26: entonces 26+62=88 es un palíndromo. Si el número fuera 57, entonces 57+75=132 no es un palíndromo, pero 132+231=363 sí lo es.

En general, la iteración $a_1\ldots a_n\to a_1\ldots a_n+a_n\ldots a_1$ siempre parece llevar a un palíndromo. ¡Pero, el punto es que esto no funciona para 196!

Este problema es bien conocido, y existen numerosas pruebas numéricas de ello, véase http://en.wikipedia.org/wiki/Lychrel_number y http://www.p196.org/ . Me preguntaba, ¿hay algún avance teórico sobre este tema? O al menos, ¿a qué área matemática pertenece este problema? Muchas gracias.

Answer 1

El progreso (que puede no ser reciente), aparece en la programación de trucos para empujar las iteraciones a partir de 196 en más y más millones de dígitos.

No es cierto que recorrer casi siempre parece conducir a un palíndromo. A menos que la iteración conduce a un palíndromo "bastante rápido", uno casi nunca parece llegar a un palíndromo. Para un número par de dígitos, una eventual palíndromo es bastante probable. Como el número de dígitos crece la probabilidad parece disminuir rápidamente. Deje $s(x)$ será el resultado de aplicar a la inversa y de la operación de agregar a $x$. No hay ninguna prueba que descarta la posibilidad de que para todos los $x$ no es un porcentaje ($j$ con $s^j(x)$ un palíndromo, pero parece muy poco probable. Si examinamos una gran variedad de números y clasificar a $x$ como probablemente nunca llegar a un palíndromo si ninguno de $s(x),s^2(x),..s^{50}(x)$ es un palíndromo, a continuación, vamos a tener algunos errores (probablemente bajo $1\\%$) que puede ser descubierto por empujar a $s^{500}(x)$. Pero si empujamos que ahora, o incluso sólo a$s^{300}(x)$, entonces es probable que nunca haya un error (que podemos descubrir.)

No es (según Wikipedia) un número de 19 dígitos que llega a un palíndromo después de 261 iteraciones y este es el registro actual. Traté de 500 aleatoria de 10 dígitos enteros (en realidad, enteros aleatorios en $10^{10}.$) De ellos, 224 fueron a 300 iteraciones sin un palíndromo. Hubo 13 casos que no llegan a un palíndromo, pero tomando en menos de 30 iteraciones. Tomaron 30,30,32,32,32,34,38,41,42,46,49,66 y 88 iteraciones.

Además de la discusión de Algunas observaciones y preguntas, en ningún orden especial:

Deje $r(x)$ ser el inverso de $x$ e $s(x)=x+r(x)$ será el resultado de aplicar a la inversa y de la operación de agregar a $x$.

• Si $x$ es un múltiplo de $11$, por lo que es $r(x)$ y, por tanto,$s(x)$, y todos los futuros itera $s^i(x)$
• si $x$ tiene un número par de dígitos, a continuación, $s(x)$ es un múltiplo de $11$
• Un palíndromo con un número par de dígitos es un múltiplo de 11.
• De la $9\cdot10^M$ palíndromos con $2M+1$ dígitos, acerca de $\frac{1}{11}$ son múltiplos de $11.$

Llame a $x$ especial si no se lleva a ocurrir en la adición $x+r(x).$, En este caso, $x+r(x)$ es un palíndromo. Llame a $x$ excepcional si $x+r(x)$ es un palíndromo, sino $x$ no es especial (es decir, lleva ocurren). Por definición, $s(x)$ es un palíndromo exactamente al $x$ es especial o excepcional.

Si $z=s(y)$, entonces cuando nos adecuadamente coinciden $z$ con $r(z)$, correspondiente dígitos serán iguales o diferentes por $1$ (en el caso de realizar inmediatamente antes de que uno pero no el otro). Aquí apropiadamente significa que cuando $z$ tiene un dígito más de $y$ que no coinciden con el líder de $1$,

Por lo tanto, si $x$ tiene un número $2M$ de los dígitos, a continuación, $s(x)$ es un múltiplo de $11$, con lo cual, si no un palíndromo, no sólo por tener algunas posiciones, que debe ser igual difieren por $1$ y tal vez tener un líder de $2M+1$st dígitos que es un $1$. Si $x$ tiene un número impar de dígitos, a continuación, casi la misma es verdadera.

Los comentarios anteriores muestra que los enteros de la forma $s(x)$ son bastante especiales. ¿Qué se puede decir acerca de los números de la forma $s^2(x)$, $s^3(x)$ etc? Ciertamente, por $s^6(x)$ (y generalmente antes) hemos tenido un número par de dígitos en algunos etapa anterior y por lo tanto están en un múltiplo de $11$ a partir de entonces.

Claramente debe haber muchas soluciones de $s(x)=s(y)$ con $x \ne y$ desde el conjunto de imágenes es mucho más escaso. Podemos ver que directamente porque para $y=\sum_0^{N-1}a_i10^i$ tenemos $s(y)=\sum_0^{N-1}(a_i+a_{N-1-i})10^i.$ Esto generalmente presenta muchas posibilidades para aumentar de $a_i,a_{N-1-i}$ por $1,2,3$ o incluso más inferior y el otro por una cantidad igual para conseguir $x$ con $s(x)=s(y).$

Recordar que todos los $y$ con $s(y)$ un palíndromo es especial o excepcional (y viceversa). Aproximadamente el $(1.8)^{-N/2}$ de la $N$ dígitos enteros $z$ son especiales y no veo que saber también que $z=s^j(x)$ para algunos $x$ cambios. Así que para pequeños iniciando $x$ no es una buena oportunidad de llegar a un número especial ya que en repetidas ocasiones se aplican $s$. Sin embargo, esta posibilidad se hace más pequeña a medida que el número de dígitos que se eleva. Esto sugiere que si se itera $s(x)$ se mete en todos los dígitos sin ejecutar en un palíndromo, es poco probable que alguna vez llegar a uno.

Aquí está una cierta justificación de la cuenta: Deje $N=2M$ ser incluso. Hay $9\cdot10^{N-1}$ enteros $x=\sum_{0}^{N-1}x_i10^i$ con $N$ dígitos. Las proporciones de estos que son especiales y excepcionales son fáciles de dar exactamente, pero menos de $\frac{1}{1.8^M}$ de ellas son especiales y y menos de $\frac{1}{10^M}$ son excepcionales. Esto es porque hay $100$ formas de seleccionar cada una de las $M$ pares de $x_i,x_{N-i-1}$ (a excepción de $90$ formas para recoger $x_0,X_N$.) Para ser especial sólo hay $55$ opciones con $x_i+x_{N-i-1}\le 9$ (con la excepción de $45$ para $i=0$). Un número es excepcional si cada par $x_i,x_{N-1-i}$ tiene suma $0$ o $11.$ (creo que he demostrado que a mi satisfacción.) Para $N=2M+1$ las proporciones son del mismo teniendo en cuenta la central de dígitos.

Pensamientos finales Aquí es más fácil de problema relacionado con lo que podría ser llamado el 49 problema, no sé si hay un 49+49=98 problema a pesar de que acabamos de ver en el 98+98=196 problema. 196+196=392 y he pasado tiempo en el 392 problema , pero no está relacionado. Aquí está el 49 problema: Llamar a un número entero $z$ muy incluso si todos los dígitos son incluso (lo que es equivalente,si $z=d(x)=x+x$ una $x$ con todos los dígitos menos de $5$) .

Q: para los que $n$ no $n,d(n),d^2(n),\cdots$ llegan en un muy parejo entero?

Hasta 20001 hay un único motor de arranque que se obtiene una muy parejo número después de 47 doblajes, pero no antes. Curiosamente 49,98,196,392,... es el primer ejemplo que nunca parece llegar a un número. Incluí este ejemplo porque pensé que iba a haber algunos enteros que seguramente nunca llevar a un muy parejo número. Mi propuesta había pruebas de que $x,d(x),d^2(x),\cdots$ es finalmente periódico mod $10^j$ cualquier $j$, por lo que uno podría necesitar para encontrar el adecuado a $j$ donde cada miembro de la ciclo tuvo una dígitos impares. Sin embargo, ahora veo que el $\mod 10^j$ órbita tiene una longitud de $4\cdot 5^{j-1}$, por lo que casi seguramente no tienen un $j$ dígitos muy parejo miembro (que puede ser el final de la cola de mucho, mucho, mucho más enteros con un montón de espacio para impar de dígitos). Sin embargo parece claro que cuando el número de dígitos es pequeña, existe una probabilidad razonable de chocar en un número par, pero que va a la $0$ exponencialmente en $d$ para un "azar" $d$-número de dígitos. Sería bueno encontrar una invariante para su problema, o para este, (similar a la propuesta de reducir el mod $10^j$ aquí), que podría descartar un palíndromo. Corto de algo como esto parece difícil imaginar una prueba definitiva (como opuesto a probabilístico heurística) de nunca llegar a un palíndromo.

Answer 2

He aquí algunos cálculos heurísticos. Sea $r(x)$ sea la inversión de $x$ en base 10, $s(x)=x+r(x)$ et $f(x)=s(x)$ si $x$ es distinto de cero módulo 10, y $f(x)=s(s(x))$ si $x$ es múltiplo de 10.

Los palíndromos de la secuencia $s(x),s^2(x),s^3(x),\dots$ son los mismos que los de la secuencia $f(x),f^2(x),f^3(x),\dots$ [Edición: según los comentarios esto no es 100% cierto], y $f$ crece exponencialmente rápido: $$100 x > f(x) > \frac{11}{10} x.$$ Las constantes aquí no son tan importantes: la secuencia crece exponencialmente. Tarea: ¿qué es $\sup f(x)/x$ ? [Editar: sigue siendo cierto que $s$ crece exponencialmente rápido en promedio, y eso es suficiente para justificar todo abajo].

¿Qué probabilidad hay de que un número aleatorio sea palindrómico? Entre $a\cdot 10^k$ y $(a+1)\cdot 10^k$ (con $1\leq a \leq 8$ ), hay $10^{\lfloor k/2 \rfloor}$ palíndromos. Así que un número aleatorio de tamaño alrededor de $N$ tiene una probabilidad en torno a $1/\sqrt{N}$ de ser un palíndromo (esto es burdo, pero sólo estamos hablando de heurística). A grandes rasgos, entonces, la probabilidad de que ninguno de $f(x),f^2(x),f^3(x),\dots$ siendo palíndromos, suponiendo la independencia, i $$p_x:=P(\text{$ x $ is Lychrel}) \approx \prod_{i=1}^\infty \left(1-\frac{1}{\sqrt{(11/10)^i x}}\right).$$ Continuando, $$\log(p_x) \approx \sum_{i=1}^\infty \log(1-1/\sqrt{(11/10)^i x})\approx -\sum_{i=1}^\infty 1/\sqrt{(11/10)^i x} \approx -\frac{20}{\sqrt{x}},$$ donde el $\approx$ símbolo significa que no soy preciso salvo en lo que creo que importa. Todo esto viene a $p_x \approx c^{1/\sqrt{x}}$ para algunos $0 < c < 1$ .

Suponiendo que todavía pueda hacer cálculos, esto significa que $p_x\to 1$ y así $\sum_{x=1}^\infty p_x$ diverge, por lo que por los lemas de Borel-Cantelli hay infinitos números de Lychrel. Para cualquier $x$ tiene una probabilidad no nula de ser Lychrel, y la mayor parte de esa probabilidad está ligada a las primeras iteraciones de $f$ . A medida que 196 sobrevive a las primeras tantas iteraciones, se hace cada vez más improbable (pero no imposible) dar con un palíndromo.

Answer 3

He aquí algunas ampliaciones de los comentarios de Aaron Meyerowitz. (Edición: Como Aaron señala en los comentarios, mi afirmación principal aquí es en realidad errónea).

Como señala Aaron, está claro que si se calcula la suma $s(x) = x + r(x)$ no implica ningún acarreo, entonces $s(x)$ es un palíndromo. En este caso llamamos $x$ "especial". Si la informática $s(x)$ conlleva acarreos (es decir, $x$ no es especial) pero $s(x)$ es sin embargo un palíndromo, llamamos a $x$ "Excepcional". Aaron pregunta cuán comunes son los números excepcionales.

Afirmo que los números excepcionales sólo se dan en una situación muy concreta, y que esto nos da una condición necesaria y suficiente para que $s(x)$ ser un palíndromo. En concreto, afirmo que un cálculo portador de $s(x)$ resulta en un palíndromo si y sólo si el acarreo ocurre en el primer y último lugar del número, y resulta en que los dos primeros dígitos y los dos dígitos finales son uno. Básicamente, la regla es la siguiente $s(x)$ es un palíndromo si no hay ningún acarreo en su cálculo, excepto en una situación muy específica. Esto se aplica a todas las bases.

Dado un número entero no negativo $n$ y una base $b \geq 2$ escribiremos $\bar{n}$ para denotar el número de dígitos en $n$ 's base $b$ representación. Escribimos $n_i$ para denotar la $i$ dígito de la izquierda, con $n_1$ el primer dígito (menos significativo), y $n_{\bar{n}}$ siendo el último dígito (el más significativo).

Escribiremos $n_{-i}$ abreviar $n_{\bar{n} - i + 1}$ . Este es el dígito "correspondiente" a $n_i$ a la inversa de $n$ . Tenemos $n_{-i} = r(n)_{i}$ .

Dado un número $n$ un "carry" es un índice $1 \leq i \leq \bar{n}$ tal que $n_i + n_{-i} \geq b$ . Es un lugar en el que se lleva a cabo una operación informática. $s(n)$ . Si $n$ no tiene cargas, entonces $s(n)$ es un palíndromo.

Definir un "acarreo interno" como un acarreo $i$ où $1 < i < \bar{n}$ . Un "carry externo" es un carry $i$ où $i = 1$ o $i = \bar{n}$ . Un "acarreo exterior excepcional" es un acarreo exterior es un acarreo exterior donde, dejando que $m = s(n)$ tenemos

$ m_{\bar{m}} = m_{\bar{m}-1} = m_{\bar{n}} = m_2 = m_1 = 1. $

Es decir, en un acarreo externo excepcional, los dos primeros dígitos y los dos últimos dígitos de $s(n)$ son todos $1$ .

Proposición. $s(n)$ es un palíndromo si cada acarreo de $n$ es un transporte exterior excepcional.

(De izquierda a derecha.) Let $m = s(n)$ y supongamos $m$ es un palíndromo. Supongamos que hay un acarreo exterior. Entonces $m_{\bar{m}} = 1$ . Entonces $m_1 = 1$ . Entonces

$m_{\bar{m}-1} = m_{\bar{n}} = n_1 + n_{\bar{n}} - b = m_1 = 1.$

Entonces $m_2 = m_{\bar{m}-1} = 1$ . Así que si hay un acarreo externo, es excepcional. Ahora supongamos que hay un acarreo interior, y que $i$ sea el acarreo interior más pequeño. (Obsérvese que $i \leq \lceil \frac{\bar{n}}{2} \rceil$ ya que si $i$ es un acarreo, entonces $-i$ también es un carry).

Para empezar, supongamos que no hay transporte exterior. Entonces $i$ es el acarreo más pequeño. Entonces

$m_{i-1} = n_{i-1} + n_{-(i+1)}.$

$-i$ es también un carry, por lo que hay un carry en $-i+1$ . Pero $-i$ es el carry mayor, por lo que no hay carry desde $-i+1$ . Así que

$m_{-i+1} = m_{-(i-1)} = n_{-(i-1)} + n_{--(i-1)} + 1 = n_{i-1} + n_{-(i-1)} + 1 \neq m_{i-1},$

así que $m$ no es un palíndromo. Así que en el caso en el que no hay acarreo exterior, no hay acarreo interior. Ahora supongamos que hay un acarreo exterior. El acarreo exterior es excepcional, y entonces

$m_{\bar{m}} = m_{\bar{m}-1} = m_{\bar{n}} = m_2 = m_1 = 1.$

Si $i \geq 3$ entonces podemos argumentar como en el caso en que no hay acarreo exterior, ya que tenemos que no hay acarreo en el $i$ º lugar. $i \neq 1$ ya que $i$ es interior. Supongamos que $i = 2$ . Entonces hay un carry de $m_{\bar{n}-1}$ en $m_{\bar{n}}$ . $n_1 + n_{\bar{n}} = b+1$ (es decir, 11 en base $b$ ), ya que hay un acarreo exterior y $m_1 = 1$ . Así que

$m_{\bar{n}} = n_1 + n_{\bar{n}} - b + 1 = b + 1 - b + 1 = 1 + 1 = 2,$

contradictorio $m_{\bar{n}} = 1$ . Así que no hay transporte interior, y hemos terminado con el caso de izquierda a derecha.

(De derecha a izquierda.) Supongamos que cada carry para $n$ es un transporte exterior excepcional. Si no hay acarreos, entonces $m = s(n)$ es un palíndromo. Supongamos que hay un acarreo exterior excepcional. Entonces $m_i = m_{-i}$ para todos $i \in \{1,2,\bar{m},\bar{m}-1\}$ por definición, y $m_{i} = m_{-i}$ para todos $2 < i < \bar{m}-1$ por la ausencia de transporte interior.

Los comentarios y las críticas son bienvenidos; sospecho que la prueba podría perfeccionarse, ¡y de hecho podría estar equivocada!