Página de inicio

196 Y OTROS NUMEROS LYCHREL

Cita al azar

Sitio Enlace

Bienvenido a p196.org!

Desde uno de los correos electrónicos de Jason:

Tengo mucha curiosidad. Recuerdo que leí en alguna parte que, de todos los números menos de 5.000 o algo así, todos los números correspondían a una de 3 semillas (supongo que una de 196, 879, ó 1997 - a partir de los números anteriores de este correo), y no podía yo t 'creer. Me hubiera asumido que sería de 100 de ellos. Fue muy interesante que todos ellos cayeron en 3. Esto hace que parezca que hay algo muy especial con los números - que todos los demás que no se conviertan en palíndromos caer en uno de ellos - si no lo hacen, se convierten en palíndromos! Podría ayudar a proporcionar los datos para demostrar, una vez por todas, que 196 no va a resolver fuera!

Lychrel Numbers and Palindromes

Personalmente, me sentiría triste para encontrar una prueba de que 196 no tiene solución palindrómicas. He pasado mucho tiempo en ese número, y... Bueno... Usted entiende.

Por otro lado, me gustaría encontrar algo común a los números que no tienen solución palindrómicas! Es por eso que he decidido que es necesario que haya una lista de ellos en alguna parte. Así que la gente pueda verlas, empuje con un palo, y generalmente les dan un poco de pensamiento. ¿Hay algo en común entre ellos? Sabemos que 196 es el más pequeño, lo que es el más grande que conocemos? (Infinito no cuenta. Ya he decidido que Infinity en sí debe ser un palíndromo. :-))

Jason, Istvan y yo hemos hablado acerca de estos números. Las siguientes son algunas de las notas que he recopilado de los debates, así como la mejor opción probable para eficiente en busca de los próximos mayor número Lychrel... La primera mitad de la obra a continuación puede ser acreditado a Jason Doucette. Istvan es el que me lo explicó, pero creo que él estaba explicando lo que Jason había hecho ya para buscar de manera eficiente en su trabajo más largo retrasadas palíndromo. Traté de volver a escribir, simplemente, para que la gente como yo podía entenderlo, con un poco de pensamiento. Creo que la mayoría de la segunda etapa es el trabajo de István e ideas. (Es difícil a veces para recordar lo que han contribuido, y asegurarse de que son reconocidos!) Me cabe duda de que he añadido mucho a la discusión.... :-(

Sería muy fácil comenzar con una lista de todos los números entre dos puntos dados. Decir, 0-1,000,000.

El primer paso obvio para mí, sería ir por la lista y eliminar los números que ya son palíndromos. Esto eliminará un montón de números desde el principio.

Una de las primeras cosas que debemos hacer es encontrar y eliminar todos los números que seguirá el mismo hilo en el largo plazo. Por ejemplo, 196, 295, 394, 493, 592, 691 todos formarán 887 en la primera iteración, y entonces todo después de que será idéntico para todos los 6 números. De buenas a primeras, tendríamos una gran cantidad de redundancia de tiempo de cálculo, si no eliminar los otros números de 196. El ahorro de tiempo sería considerable!

Así que realizaría 1 iteración de cada uno de esos números, y encuentra que todo el plomo a 887, a continuación, eliminar 295, 394, 493, 592, y 691 de nuestra lista.

Desde este punto de vista, tenemos que examinar los pares de dígitos correspondiente, el primero y el último, el segundo y el último uno menos, la tercera y última menos 2 etc Siempre que estos pares de números dan la misma suma, el reversión o procedimiento además se producen el mismo resultado.

Hay 18 pares de dígitos exterior que se traducirá en cantidades diferentes.

diez primeros:
1xx0
1xx1
1xx2
...
1xx8
1xx9
Y los siguientes ocho:
2x... x9
3x... x9
4x... x9
5x... x9
6x... x9
7x... x9
8x... x9
9x... x9

Cualquier otra combinación dará lugar a un número duplicado después de la primera iteración.

A continuación, hay 19 pares de dígitos interior (porque en este caso se permitirá el primero de los dos a cero).

x0xx...
xx0x x0xx...
xx1x x0xx...
xx2x x0xx...
xx3x etc

Esto funcionará para todos los números pares de dígitos. Si el número se ha examinado un número impar de dígitos, se debe multiplicar por diez, debido a los dígitos en el centro:


xxx0xxx
xxx1xxx ...

xxx9xxx

Como puede ver, para calcular, por ejemplo, cuántas iteraciones se necesitan para controlar todos los 7 números de dos dígitos que difieren en las cantidades par de dígitos, debemos multiplicar estos coeficientes:

18 * 19 ^ 2 * 10 = 64980 iteraciones (en lugar de 9000000)

18 es el par externo de dígitos, 10 es para el dígito central, 19 ^ 2 es para los dos pares de interior. Usted puede ver cuánto más rápido de esta búsqueda sería en el largo plazo.

Incluso podemos construir una fórmula general para calcular el número de números para comprobar:

18 * 19 ^ ((n-2) div 2) * 10 ^ (mod n 2)

n

es la longitud del número, y debe ser mayor que 1. La parte 10 ^ (mod n 2) le da 10 para longitudes impares, 1 para longitudes de hasta.

La siguiente tabla puede ayudar a demostrar lo siguiente:

NOTA: Esto no es completa. Es sólo un ejemplo de lo que habría que hacer para verificar los números de entre los dígitos 3 y 17.

Número de Dígitos Total Dígitos Números Ser Facturado Razón Cada Enésima Ser Facturado
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SUMA:
900
9000
90000
900.000
9000000
90000000
900 millones
9000000000
90000000000
900000000000
9.000.000.000.000
90.000.000.000.000
900.000.000.000.000
9.000.000.000.000.000
90.000.000.000.000.000
99.999.999.999.999.900
180
342
3420
6498
64980
123.462
1234620
2345778
23457780
44569782
445697820
846825858
8468258580
16089691302
160896913020
186 819 193 422
20.000000%
3.800000%
3.800000%
0.722000%
0.722000%
0.137180%
0.137180%
0.026064%
0.026064%
0.004952%
0.004952%
0.000941%
0.000941%
0.000179%
0.000179%
0.000187%
5
26
26
138
138
728
728
3836
3836
20193
20193
106.279
106.279
559.364
559.364
535.276

lo tanto, si sólo vamos números de búsqueda entre las 3 y 17 dígitos, hay 186 819 193 422 números que debe ser revisado con el fin de marcar sólo una de las consecuencias de cada hilo.

Segundo paso: filtrar el número de semillas independiente

.

El siguiente paso sería empezar al revés / añadir proceso para cada uno de los números restantes y eliminar los números de arriba para cada uno. Por ejemplo, si íbamos a 9 dígitos, 887 / 7436 / 13783 / 52514 / 94039 / 187088 / 1067869 / 10755470 / 18211171 / 35322452 / 60744805 / 111589511 / 227574622 / 454050344 y 897100798 todo tendría que ser removido de la lista, ya que todos están en el hilo de 196. Al mismo tiempo, los números que llevan a un palíndromo, serán eliminados. Por ejemplo, 89, 187, 968, 1837,... 8.813.200.023.188 todo sería eliminado, ya que 89 se convertirá en un palíndromo en 24 iteraciones.

Cuando haya terminado, cualquier cosa a la izquierda en la lista, debe ser un número de semillas...

Admito que esto no es la única forma de búsqueda de estos números. Puede que no sea el más fácil de programar. Puede que no sea ni de lejos la manera más rápida de encontrar estos números. Pero es una manera que parece razonable.