Page d'Accueil

196 ET AUTRES NUMÉROS LYCHREL

Random Quote

Site Liens

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!

Lychrel Numbers and Palindromes

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.

Les dix premiers:
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).

x0xx...
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 * 19 ^ 2 * 10 = 64.980 itérations (au lieu de 9.000.000)

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)

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.