Das Palindrom-Spielgelsummen-Problem

Letztmalig dran rumgefummelt: 16.06.08 16:20:04

	Man nehme eine natürliche Zahl, bilde die Spiegelzahl, addiere beide i und wiederhole den Vorgang mit der Summe. Nach einiger Zeit ergibt sich eventuell ein Palindrom - (d. h. eine Zahl, die mit ihrer Spiegelzahl übereinstimmt, die also vorwärts und rückwärts gelesen gleich lautet). Bei einigen Zahlen lässt sich dies mit einem einzigen Schritt erreichen: 18 + 81 → 99; bei anderen benötigen wir zwei: 19 + 91 → 110 + 011 → 121 oder drei Schritte: 68 + 86 → 154 + 451 → 605 + 506 → 1111 Es ist offensichtlich, dass bei allen zweiziffrigen Zahlen, deren Quersumme kleiner als 10 ist, der erste Schritt ein zweiziffriges Palindrom liefert. Wenn die Quersumme 10, 11, 12, 13, 14, 15, 16 oder 18 beträgt, erhält man das Palindrom nach 2, 1, 2, 2, 3, 4, 6 bzw. 6 Schritten. Eine - Ausnahme bilden die Zahlen mit - Quersummen 17: beginnt man mit 89 (oder 98), erhält man erst nach 24 Schritten das Palindrom 8813200023188.
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Informationen 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren Logo für das Palindrom-Spiegelsummen-Problem inhaltlich auf korrektem Stand - evtl. partiell unvollständig ;-) Informatik-Profi-Wissen
	Quellen: LOG IN - Heft 3/93 (2007) Seite 70 ff.

1. Problembeschreibung

	Der kalifornische Mathematiker Charles W Trigg fand 249 Zahlen kleiner als 10 000, die - als Startzahlen des Spiegel-Additions-Prozesses genommen - nach hundert Schritten noch kein Palindrom ergaben. Die kleinste davon ist 196. Bei dieser Startzahl brach Harry J. Saal nach 237 310 Schritten den Prozess ergebnislos ab. Clifford Pickover untersuchte die Zahl 879, fand aber nach 19 000 Schritten kein Palindrom. Auch 1997 als Startzahl führte nach 8 000 Schritten nicht zum Erfolg. Außer den 249 Ausnahmen erzeugen alle Zahlen unter 10 000 ein Palindrom in höchstens 24 Schritten. Das größte, nämlich 16668488486661, wird von 6999 (bzw. 9996) und von 7998 (bzw. 8997) in zwanzig Schritten erzeugt.
	Das Palindromproblem lautet: Ergibt sich bei jeder Startzahl des Spiegel-Additions-Prozesses nach endlich vielen Schritten ein Palindrom? Die Frage ist bis heute nicht beantwortet; es ist aber bisher auch nicht bewiesen, dass sie nicht entscheidbar ist. Wir haben damit eines der Probleme vor uns, das sich jedem Viertkläßler und jedem Lateinlehrer erklären lässt - und das andererseits so schwierig ist, dass die Mathematiklehrer mit ihrem ausgefeilten gedanklichen Instrumentarium und all ihrer Genialität bis heute gescheitert sind. Mathematiker und - vielleicht mehr noch - mathematisch interessierte Laien fragen sich: „Was ist z. B. an der Zahl 196 denn besonderes daran, dass sie ein so außergewöhnliches Verhalten zeigt?" Wir wollen um einen Überblick über die Schrittzahlen im Spiegel-Additions-Prozess zu gewinnen und damit wenigstens Teilergebnisse zu erzielen, den Computer einsetzen. Aufgabe 1: Schreiben Sie ein Computerprogramm, das nach Eingabe einer Startzahl den Spiegel-Additionsprozess durchführt und - falls ein Palindrom entstanden ist, dieses selbst sowie die Anzahl der Schritte nennt.
	Der russische Forscher Dnagiew Resalg nennt eine natürliche Zahl, die - als Startzahl des Spiegel-Additions-Prozesses verwendet - nach mindestens 10 000 Schritten noch auf kein Palindrom geführt hat, eine derzeit nicht entscheidbare Zahl (DNE-Zahl). Die drei kleinsten wesentlich voneinander verschiedenen DNE-Zahlen sind 196, 879, und 1997. Bei dieser Aufzählung wurde beispielsweise 691 nicht berücksichtigt, weil diese Zahl zum gleichen Spiegel-Additions-Prozess führt wie 196. Wir nennen zwei Zahlen miteinander verwandt, wenn sie - als Startzahl im Spiegel-Additions-Prozess genommen - auf die gleiche Zahl führen. So sind z. B. 69 und 264 verwandt, da 69 → 165 → 726, aber auch 264 → 726 gilt. Miteinander verwandte Zahlen sind als nicht wesentlich voneinander anzusehen und daher bei der Suche zu übergehen. Aufgabe 2: Ermitteln Sie alle wesentlich voneinander verschiedenen DNE-Zahlen. Interessant daran sind natürlich nicht die nackten Zahlen, sondern die - möglichst effizienten - Algorithmen.

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	Für kleine Mengen M ist das Problem empirisch durch ausprobieren möglich! Für große Mengen existieren allerdings keine anderen Verfahren, als genau diese: ausprobieren jeden Elements mit jedem - das sind dann aber schon bei 10 Elementen 210 Möglichkeiten.

3. Lösungsalgorithmus

	Nimm die vorgegebene Zahl - fülle sie auf vier Stellen auf. Ergibt sich Gleichheit in allen vier möglichen Stellen, so verabschieden wir uns von der Zahl - sie ist keine Zahl innerhalb des Definitionsbereiches - was wir selbstverständlich softwartechnisch exakt wegfangen, wobei wir Oma und/oder Katze nutzen! Wir erhalten in jedem Fall der verbleibenden Restmenge vier Stellen (ungleich in mindest einer Position) und bilden daraus die jeweils kleinste und größte ziffernfolge als Zahl. Von der jeweils größeren subtrahieren wir die jeweils kleinere und verfahren damit, bis wir entweder 6174 oder eine Tiefe von 7 erreicht haben (was im Worst-Case gleichzeitig eintritt).

4. Programmvorschläge

	Hannes Uhlig hat unser Vorschläge konsequent aufgegriffen und einschließlich der Problematik Oma und Katze ein Programm des Kaprekar-Algorithmus notiert, in welchem schon einige Kerngedanken eines sauberen - eben noch nicht objektorientierten Programmieirstils zusammenlaufen.

5. Zusammenfassung

6. Weiterführende Informationen

	War 'ne tolle Sache (zumindest für mich als Lehrer), einmal ein Schuljahr lang mit Schülern über doch die Grenzen von Programmiersprachen tangierende Probleme zu diskutieren, diese auszuloten, Algorithmen zu finden und wieder wegzuwerfen. Dümmer geworden ist dabei wahrscheinlich keine der betroffenen Seiten, die Schüler werden's teilweise einige Monate später an Universitäten bemerken ;-) Alles war im Rahmen des Möglichen: es anstrengend (was es ja sein soll), aber machbar - unten kann man einige Ergebnisse einsehen. Alles, was präsentiert wird, ist Wissensstand  Juni 2008 ;-)
	die Primzahl-Zwillingssuche der Kaprekar Algorithmus das 153-Problem - Narziß-Zahlen das Autoquadratzahlenproblem die Schmidtzahlen Pythagoräische Tripel Pascal-Zahlen die befreundeten Zahlen die Polynomzahlen die Goldbach-Vermutung das Palindrom Spiegelsummen-Problem die Perfect Numbers
	die Zahlenteiler GGT KGV   die Primzahlsuche - zumindest die ersten Beschreibungen sind trivial ;-) die Pseudoprimzahlen Quersummenermittlung Primzahlfaktorisierung

7. Links zum Thema

	http://de.wikipedia.org/wiki/Primzahlpalindrom

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem das 153-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost am 14. April 2008