Bienvenue à p196.org!
De l'un des e-mails de Jason:
Je suis très curieux. Je me souviens avoir lu quelque part que, sur tous les numéros de moins de 5000 ou quelque chose comme ça, tous les numéros tombé dans une des 3 graines (Je suppose que l'un des 196, 879, ou 1997 - à partir des chiffres ci-dessus dans cet e-mail), et je ne pouvais pas t 'y croire. J'aurais cru qu'il y aurait 100 d'entre eux. Il était très curieux que ils sont tous tombés en 3. Il nous fait croire qu'il ya quelque chose de très spécial avec ces chiffres - que tous les autres qui ne deviennent pas palindromes tomber dans l'un d'eux - s'ils ne sont pas, ils deviennent des palindromes! Elle pourrait aider à fournir des données pour prouver, une fois pour toutes, que 196 ne résoudra jamais les!
Personnellement, je serais triste de trouver une preuve que 196 n'a pas de solution palindrome. J'ai passé beaucoup de temps sur ce nombre, et... Eh bien... Vous comprenez.
D'autre part, je serais ravie de trouver quelque chose de commun aux numéros qui n'ont pas de solution palindrome! C'est pourquoi j'ai décidé qu'il doit y avoir une liste de quelque part. Alors que les gens puissent les regarder, les pousser avec un bâton, et plus généralement de leur donner un peu de réflexion. Y at-il un point commun entre eux? Nous savons que 196 est le plus petit, ce qui est le plus grand celui que nous connaissons de? (Infinity ne compte pas. J'ai déjà décidé que Infinity se doit être un palindrome. :-))
Jason, Istvan et moi avons discuté de ces chiffres. Ce qui suit sont quelques-unes des notes que j'ai compilées à partir des discussions, ainsi que la meilleure approche probables de efficacement la recherche de la prochaine plus grand nombre Lychrel... La première moitié de l'ouvrage ci-dessous peut être attribuée à Jason Doucette. Istvan est celui qui me l'a expliqué, mais je crois qu'il était en expliquant ce que Jason avait déjà fait pour la recherche efficace dans son travail la plus longue Palindrome Tardive. J'ai essayé de réécrire tout simplement, pour que les gens comme moi pourrait-il comprendre, avec un peu de réflexion. Je pense que la plupart de la deuxième étape est un travail d'Istvan et des idées. (Il est parfois difficile de se rappeler ce qui a contribué, et de s'assurer qu'ils sont reconnus!) Je doute que j'ai ajouté beaucoup à la discussion... :-(
Il serait assez facile de commencer par une liste de tous les nombres compris entre deux points donnés. Dis, 0-1,000,000.
La première étape évidente pour moi, serait de passer par la liste et supprimez tous les numéros qui sont déjà palindromes. Cela permettra d'éliminer une série de chiffres dès le départ.
Une des premières choses que nous devons faire est de trouver et d'éliminer tous les numéros qui suivent le même fil sur le long terme. Par exemple, 196, 295, 394, 493, 592, 691 seront de toute forme 887 à la première itération, et puis tout ce qui suit sera identique pour tous les 6 numéros. Dès le départ, nous aurions beaucoup de redondance de temps de calcul, si nous n'avions pas d'éliminer les autres nombres de 196. Le gain de temps serait considérable!
nous effectuer 1 itération de chacun de ces numéros, savoir qu'ils conduisent tous à 887, puis supprimez 295, 394, 493, 592, et 691 de notre liste.
De ce point de vue, nous devons examiner les paires correspondantes chiffres, le premier et le dernier, le deuxième et le dernier en moins, le troisième et dernier moins 2 etc Chaque fois que ces paires de nombres donnent la même somme, le inversion ou de la procédure sera plus le même résultat.
Il ya 18 paires de chiffres externe qui se traduira par des sommes différentes.
1xx0
1xx1
1xx2
...
1xx8
1xx9
Et les huit suivants:
2x... x9
3x... x9
4x... x9
5x... x9
6x... x9
7x... x9
8x... x9
9x... x9
Toute autre combinaison donnera lieu à un numéro en double après la première itération.
Ensuite, il ya 19 paires de chiffres intérieure (car dans ce cas nous permettons le premier de la paire à zéro).
xx0x x0xx...
xx1x x0xx...
xx2x x0xx...
xx3x etc
Cela fonctionne pour tous les numéros de même chiffre. Si le nombre d'examen a un nombre impair de chiffres, il faut multiplier par dix, en raison du chiffre dans le milieu:
xxx0xxx
xxx1xxx ...
xxx9xxx
Comme vous pouvez le voir, pour calculer, par exemple, comment de nombreuses itérations sont nécessaires pour vérifier tous les 7 chiffres qui diffèrent dans les sommes de deux chiffres, il faut multiplier ces coefficients:
18 est pour la paire extérieure de chiffres, 10 est le chiffre du milieu, 19 ^ 2 est pour les deux paires intérieure. Vous pouvez voir comment beaucoup plus vite cette recherche serait sur le long terme.
On peut même construire une formule générale pour calculer le nombre de numéros à vérifier:
18 * 19 ^ ((n-2) div 2) * 10 ^ (2 mod n)
est la longueur du nombre, et devrait être supérieur à 1. La partie 10 ^ (2 mod n) donne 10 pour les longueurs impaire, 1 pour des longueurs de même.
Le tableau suivant peut aider à démontrer:
NOTE: Ce n'est pas complète. C'est seulement un exemple de ce qui aurait à faire pour vérifier les numéros entre les chiffres 3 et 17.
| Nombre de chiffres | chiffres Total | Numéros à vérifier | Ratio | énième être vérifiée |
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 SUM : |
900 9000 90.000 900.000 9.000.000 90.000.000 900.000.000 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 64.980 123.462 1.234.620 2.345.778 23.457.780 44.569.782 445.697.820 846.825.858 8468258580 16089691302 160896913020 186819193422 |
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 20.193 20.193 106.279 106.279 559.364 559.364 535.276 |
Donc, si nous allons seulement le nombre de recherche entre 3 et 17 caractères, il ya 186 819 193 422 numéros qui doivent être contrôlés afin de vérifier que l'une des conséquences de chaque fil.
Deuxième étape: filtrage des numéros indépendants semences
.La prochaine chose à faire serait de commencer l'inverse / ajouter des processus pour chacun des autres chiffres et d'éliminer les numéros en amont pour chaque. Par exemple, si nous allions à 9 chiffres, 887 / 7.436 / 13.783 / 52.514 / 94.039 / 187.088 / 1.067.869 / 10.755.470 / 18.211.171 / 35.322.452 / 60.744.805 / 111.589.511 / 227.574.622 / 454.050.344 897.100.798 et devront tous être retiré de la liste, car ils sont tous dans le fil 196. Dans le même temps, tous les chiffres qui conduisent à un palindrome, sera supprimé. Par exemple, 89, 187, 968, 1837,... 8.813.200.023.188 seraient tous supprimés, puisque 89 deviendra un palindrome en 24 itérations.
Lorsque vous avez terminé, plus rien sur votre liste, doit être un nombre de graines...
Je reconnais que ce n'est pas le seul moyen de recherche de ces chiffres. Il ne pourrait pas être plus facile à programmer. Il pourrait ne pas être n'importe où près de la manière la plus rapide de trouver ces chiffres. Mais c'est une façon qui semble judicieuse.