249
1. Inversion:        + 942
                     -----
1. Summe:             1191 2. Inversion:       + 1911
                     ------
2. Summe:             3102
3. Inversion:       + 2013
                    ------
3. Summe:             5115

Die Formulierung des Problems:

Eine Palindrom-Zahl kann "von rechts oder links gelesen" werden (diese Aussage gilt natürlich auch für "Wort-Palindrome"). Das hier behandelte Problem wird zunächst mit Dezimalzahlen erläutert:

Man nehme eine beliebige positive ganze Zahl (z. B.: 83), schreibe die Ziffern in umgekehrter Reihenfolge auf (38), addiere die beiden Zahlen (83 + 38 = 121). Wenn das Ergebnis nicht gleich ein Palindrom ist, setze man das Spielchen fort (siehe nebenstehendes Beispiel für die Zahl 249), bis das Ergebnis ein Palindrom ist.

Das funktioniert auch mit Binärzahlen: Wenn man zum Beispiel mit der Binärzahl 11111001 startet (entspricht der Dezimalzahl 249) dann landet man nach 10 Inversionen beim Palindrom 110001101100011.

facebook   Besuchen Sie uns bitte auf facebook

Das nachfolgende Script führt diese Rechnung aus, wobei die Startzahl binär oder dezimal (wird dann umgerechnet) eingegeben werden kann. Man probiere es mit beliebigen Startzahlen:

  Eingabe als
Binärzahl      Dezimalzahl
Maximale Inversionen
(Dezimalzahl):
 
Startzahl:

Bitte Werte eintragen und dann "Rechnung starten" anklicken!

Funktioniert das immer?

Nein, durchaus nicht. Selbst im Bereich der Binärzahlen von 1 bis 100000 (entspricht der Dezimalzahl 32) gibt es drei Zahlen, die sich hartnäckig widersetzen.

Das folgende Script untersucht einen Zahlenbereich von "Anfang" bis "Ende" darauf, wie viele Inversionen benötigt werden, bis ein Palindrom entsteht. Vorsichtshalber wird wieder eine obere Grenze "Maximale Inversionen" vorgegeben, bei deren Erreichen die Rechnung abgebrochen wird (warum gerade die Voreinstellung 1200 dafür vorgesehen ist, wird weiter unten deutlich). Man probiere zum Beispiel mal den Bereich von 100000 (dezimal: 32) bis 1000000 (dezimal: 64), und man stellt fest, dass es entweder sehr schnell geht oder aber zum Abbruch führt:

  Eingabe als
Binärzahl      Dezimalzahl
Maximale Inversionen
pro Startzahl
   
Anfang: (Dezimalzahl):  
Ende:

Bitte Werte eintragen und dann "Rechnung starten" anklicken!

"Longest Delayed Palindrome"

Bereits bei relativ kleinen Binärzahlen entsteht nach dem beschriebenen Algorithmus kein Palindrom. Schon die 10110 (dezimal:22) weigert sich hartnäckig. Das ist deshalb überraschend, weil beim Arbeiten im Dezimalsystem die 196 die erste Zahl ist, für die es bisher nicht gelungen ist, ein Palindrom auf dem beschriebenen Weg zu erzeugen.

Die sich dabei aufdrängende Frage ist, ob man nur nicht hartnäckig genug probiert hat, es könnte ja bei ausreichend vielen Schritten schließlich doch ein Palindrom entstehen. Das so genannte "196er-Problem" hat zahlreiche Spezialisten herausgefordert, man hat es nicht geschafft, ein Palindrom zu erzeugen. Aber auch der Gegenbeweis, dass das auch für beliebig viele Schritte gilt, steht aus.

Vieles spricht dafür, dass es tatsächlich Startzahlen gibt, für die der beschriebene Algorithmus nicht zu einem Palindrom führt. Weil es aber für die anderen Zahlen relativ schnell geht, ist eine andere Frage interessant geworden: Welche Zahl sträubt sich besonders lange, um schließlich doch zu einem Palindrom zu führen.

Jason Doucette aus Kanada hat diese Frage für die Dezimalzahlen jahrelang untersucht und sogar einen sehr schönen Namen für das Problem gefunden: "Longest Delayed Palindrome". Seine Ergebnisse einschließlich seines "Weltrekords" habe ich hier kurz zusammengestellt.

Auch für die Binärzahlen ist diese Frage intensiv untersucht worden. Hier heißt der Weltrekordler Karl Hovekamp, der auch zahlreiche andere Palindrom-Probleme in unterschiedlichen Zahlensystemen auf seiner interessanten Internet-Site behandelt. Der von ihm angegebene Rekord zum "Longest Delayed Palindrom" im binären Zahlensystem lautet (die Rekordzahl wurde am 5.05.05 gefunden):

Die 102-stellige Startzahl

101111111010111000100010010010110101101011110110111111111011001111110010101100101101001000011110000011

(entspricht der Dezimalzahl 3796617722816690185920388040579) ergibt nach 1194 Inversionen dieses 791-stellige Palindrom:

111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000011111111000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000011110000000111100000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000001111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000011111111.

Man kann diesen imponierenden Rekord leicht mit dem oben zu findenden Script überprüfen (am einfachsten ist es, die Dezimalzahl mit "Copy-and-Paste" aufzunehmen und in das Eingabefeld zu bringen). Nach wenigen Sekunden dürfte Ihr Bildschirm so voller Einsen und Nullen sein, wie er es vorher wahrscheinlich noch nie war.

Karl Hovekamp hat sich auch eine sehr hübsche Visualisierung für die Berechnung ausgedacht, die für das genannte Beispiel so aussieht:

Visualisierung des Palindromproblems nach Karl Hovekamp

Jede der 1194 Zahlen wird durch eine vertikale Pixelreihe repräsentiert. Die schwarzen und weißen Pixel kennzeichnen Ziffern, für die bereits das spiegelbildliche Pendant existiert, schwarze Pixel stehen für eine 0, weiße für eine 1.