plazas palindrómico de palíndromos

Question

Esta pregunta está inspirada en Google reciente de la programación de la competencia (modificado ligeramente para facilitar la exposición).

Para un determinado $n$, uno de los problemas era encontrar todos positivos "justo" enteros $k$ menos de $n$ donde $k$ es "justo" si

1. $k$ es un palíndromo (en base 10, sin ceros a la izquierda)
2. $k^2$ también es un palíndromo.

Un primer resultado es que si $k$ es un palíndromo, a continuación, $k^2$ implicará la no realización si y sólo si la suma de $k$'s el cuadrado de dígitos es menor que diez. Por lo tanto, todos los palíndromos $k$ con la suma de los cuadrados de los dígitos menos de diez son "justos".

Pero puede no ser esporádico "justa" de los números? Palíndromos $k$ donde computing $k^2$ implica la realización de algunos, pero por pura casualidad $k^2$ todavía termina siendo un palíndromo?

Answer 1

He tratado de resolver el mismo problema de ayer. Me las arreglé para ataques de fuerza bruta mi camino para encontrar a todos los de la feria y la plaza (palíndromos, cuya raíz cuadrada es un palíndromo) números de 1 a $10^{14}$:

1, 4, 9, 121, 484, 10201, 12321, 14641, 40804, 44944, 1002001, 1234321, 4008004, 100020001, 102030201, 104060401, 121242121, 123454321, 125686521, 400080004, 404090404, 10000200001, 10221412201, 12102420121, 12345654321, 40000800004, 1000002000001, 1002003002001, 1004006004001, 1020304030201, 1022325232201, 1024348434201, 1210024200121, 1212225222121, 1214428244121, 1232346432321, 1234567654321, 4000008000004, 4004009004004

Mi solución era correcta, y el segundo conjunto de datos fue resuelto. Pero yo no podía encontrar una forma adecuada de calcular todos los de la feria y la plaza de los números hasta el $10^{100}$.

Le mostré a mi esposa esta mañana, y se dio cuenta de un patrón interesante de los números dentro de mi lista:

121, 10201, 1002001, 102030201, 10000200001, 1000002000001
484, 40804, 4008004, 400080004, 40000800004, 4000008000004
12321, 1002003002001,

Algunos feria y la plaza de los números volver a aparecer con el espacio de relleno. Vamos a probar más allá de $10^{14}$. La adición de algunos ceros a $1020302030406040302030201$, cuya raíz cuadrada es $1010100010101$ - un palíndromo!

Me gustaría tener a mi esposa conmigo cuando lo resuelto ayer.

No tengo un matemático explicación para este fenómeno, pero supongo que por alguna razón, cada feria y la plaza de número más allá de un cierto límite puede ser construido mediante la adición de ceros a un menor palíndromo.

Answer 2

La primera 412 de estos se tabulan en http://oeis.org/A057135/b057135.txt

Todos los listados no tienen ningún dígito superior a 2 y generalmente tienen un montón de ceros, por lo que supongo que no hay ningún esporádicos en la lista. Por supuesto, no es una prueba...

Answer 3

Durante la competición, me encontré con la primera 'feria y la plaza de los números, a continuación se busca para ellos en Sloane enciclopedia de secuencias de enteros. Su página http://oeis.org/A057135 sugiere la 'suma de los cuadrados de los dígitos es menor que 10' condición es necesario y suficiente, pero no da una prueba. No es obvio para mí.

Edit: Google ha publicado una prueba por contradicción en https://code.google.com/codejam/contest/2270488/dashboard#s=a&a=2