Willkommen bei p196.org!
Von einem Jason's E-Mails:
Ich bin sehr gespannt. Ich erinnere mich, irgendwo gelesen, dass aus all den Zahlen unter 5.000 oder so ähnlich, alle Zahlen in einer der 3 Samen (ich nehme an einer der 196, 879, oder 1997 - von den oben genannten Zahlen in dieser E-Mail) fiel, und ich konnte 't glauben. Ich würde davon ausgegangen, es wäre 100 von ihnen haben. Es war sehr interessant, dass sie alle fielen in 3. Es macht es den Anschein, dass es etwas ganz Besonderes mit diesen Zahlen -, dass alle anderen, die nicht zu tun Palindrome in einer von ihnen fallen - wenn sie dies nicht tun, sie Palindrome werden! Es könnte dazu beitragen, Daten zu beweisen, ein für alle Mal, dass 196 niemals lösen raus!
Persönlich würde ich traurig sein, um einen Beweis finden, dass 196 kein Palindrom Lösung hat. Ich habe viel Zeit auf diese Zahl ausgegeben werden, und... Nun... Du verstehst.
Auf der anderen Seite, würde ich gerne etwas gemeinsam, um die Zahlen, dass kein Palindrom Lösung haben finden! Deshalb habe ich beschlossen, dass es muss eine Liste von ihnen irgendwo sein. So dass man sie anschaut, stoßen sie mit einem Stock, und nur allgemein ihnen ein bisschen Gedanken. Gibt es eine Gemeinsamkeit zwischen ihnen? Wir wissen, dass 196 die kleinste, was die größte uns bekannte ist? (Infinity zählt nicht. Ich habe bereits entschieden, dass Infinity selbst muss ein Palindrom ist. :-))
Jason, Istvan und ich habe über diese Zahlen gesprochen. Im Folgenden sind einige der Notizen, die ich aus den Gesprächen zusammengestellt, sowie die besten wahrscheinlich Ansatz effizient Suche nach dem nächsten größeren Anzahl Lychrel... Die erste Hälfte des Werkes unten kann Jason Doucette gutgeschrieben. Istvan ist derjenige, der es mir erklärt, aber ich glaube, dass er zu erklären, was Jason hatte bereits für die effiziente Suche in seiner längsten verzögerte Palindrome Arbeit geleistet. Ich versuchte es einfach umschreiben, so dass Leute wie ich könnte es verstehen, mit ein wenig Gedanken. Ich denke, die meisten der zweite Schritt ist Istvan Arbeit und Ideen. (Es ist manchmal schwierig zu erinnern, wer was beigetragen und gewährleisten, dass sie erkannt werden!) Ich bezweifle, dass ich sehr auf die Diskussion hat.... :-(
Es wäre leicht genug, um eine Liste mit jeder Zahl zwischen zwei gegebenen Punkten beginnen. Sprich 0-1,000,000.
Der erste logische Schritt für mich, wäre durch die Liste gehen und löschen Sie alle Nummern, die bereits Palindrome. Dadurch wird das durch eine Reihe von Zahlen von Anfang an.
Eines der ersten Dinge, die wir tun müssen, ist zu finden und beseitigen alle Zahlen, die dem selben Thread auf lange Sicht folgen werden. Zum Beispiel, 196, 295, 394, 493, 592, 691 werden alle Formularfelder 887 auf der ersten Iteration, und dann alles danach wird für alle 6 Zahlen identisch. Rechts von der Fledermaus, hätten wir eine Menge Redundanz Rechenzeit, wenn wir nicht beseitigen die Zahlen außer 196. Die Zeitersparnis wäre ein erheblicher!
werdenSo würden wir durchführen 1 Iteration jeder dieser Nummern, herauszufinden, dass sie alle führen zu 887, dann 295, 394, 493 löschen, 592, und 691 aus unserer Liste.
Aus dieser Sicht haben wir auf die entsprechende Ziffer Paare prüfen haben, das erste und das letzte, das zweite und das letzte minus eins, das dritte und letzte minus 2 usw. Wenn diese Anzahl Paare geben die gleiche Summe, die Umkehrung / Ergänzung Verfahren wird zum gleichen Ergebnis führen.
Es gibt 18 äußere Zahlenpaare, die in unterschiedlichen Beträgen führt.
1xx0
1xx1
1xx2
...
1xx8
1xx9
Und die folgenden acht:
2x... x9
3x... x9
4x... x9
5x... x9
6x... x9
7x... x9
8x... x9
9x... x9
jede andere Kombination führt zu einer Reihe Duplikat nach der ersten Iteration.
Weiter gibt es 19 innere Zahlenpaare (weil wir in diesem Fall die erste der beiden zu Null werden kann).
x0xx... xx1x
x0xx... xx2x
x0xx... xx3x
usw.
Dies wird für alle noch stellige Zahlen zu arbeiten. Wenn die Zahl geprüft hat eine ungerade Anzahl von Ziffern, sollten wir um zehn multiplizieren, da die Ziffer in der Mitte:
xxx1xxx
...
xxx9xxx
Wie Sie sehen können, zu berechnen, zum Beispiel, wie viele Iterationen nötig sind, um all jene 7-stellige Nummern, die im einstelligen Paar Summen unterscheiden sich überprüfen, sollten wir diese Koeffizienten multipliziert:
18 ist für das äußere Paar von Ziffern, 10 für den mittleren einstelligen, 19 ^ 2 ist für die beiden inneren Paare. Sie können sehen, wie viel schneller diese Suche würde auf lange Sicht werden.
Wir können sogar Konstrukt einer allgemeinen Formel, die Anzahl der Zahlen berechnen zu prüfen:
18 * 19 ^ ((n-2) div 2) * 10 ^ (n mod 2)
n die Länge der Zahl, und sollte größer als 1 sein. Die 10 ^ (n mod 2) Teil gibt 10 für ungerade Längen, 1 für noch Längen.
Die folgende Tabelle kann helfen, zu demonstrieren:
HINWEIS: Das ist nicht vollständig. Es ist nur ein Beispiel, was hätte getan werden, um Zahlen zwischen 3 und 17 Zahlen zu überprüfen.
| Anzahl der Ziffern | Total Ziffern | Zahlen zu Checked | Ratio | jede n-te zu sein Checked |
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 SUM: |
900 9.000 90.000 900.000 9.000.000 90.000.000 900.000.000 9000000000 90000000000 900.000.000.000 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 3.420 6.498 64.980 123.462 1.234.620 2.345.778 23.457.780 44.569.782 445.697.820 846.825.858 8468258580 16089691302 160.896.913.020 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 3.836 3.836 20.193 20.193 106.279 106.279 559.364 559.364 535.276 |
Also, wenn wir nur gehen Suche Zahlen zwischen 3 und 17 Zahlen, es gibt 186.819.193.422 Zahlen, um zu überprüfen, um nur eine Folge der Überprüfung jeder Thread sollte.
Zweiter Schritt: Herausfiltern der unabhängigen Seed Zahlen
.Das nächste, was zu tun wäre, um das Gegenteil zu beginnen / add-Prozess für jede der übrigen Zahlen und die Beseitigung der Upstream-Nummern für jeden. Zum Beispiel, wenn wir bis 9 Ziffern, gehen 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 und würde alle haben aus der Liste entfernt werden, da sie alle in den 196 Thread. Gleichzeitig wird jede Zahl, die ein Palindrom führen, gestrichen werden. Zum Beispiel, 89, 187, 968, 1837,... 8.813.200.023.188 würden alle gestrichen werden, da 89 a in 24 Iterationen Palindrom werden wird.
Wenn Sie fertig sind, verlassen, alles auf Ihrer Liste sollte eine Anzahl Samen werden.....
ich zugeben, dass dies nicht der einzige Weg, um diese Zahlen zu suchen. Es ist vielleicht nicht das einfachste zu sein Programm. Es ist vielleicht nicht überall in der Nähe der schnellste Weg, um diese Zahlen zu finden. Aber es ist eine Möglichkeit, dass eine solide scheint.