Das 153-Problem

Letztmalig dran rumgefummelt: 13.06.08 14:24:35

	Seit den Tagen der alten Babylonier und denen des Pythagoras von Samos blüht die Numerologie: eine Lehre, die den Zahlen neben ihrer mathematischen weitere Bedeutungen und Wirkungen zuschreibt. Einige numerologisch bedeutsame Zahlen: die Pythagoräer verehrten die heilige Vierzahl (Tetraktys) mit der charakteristischen Gleichung 1+2+3+4=10 in der Bibel wird den Zahlen 1 bis 10 und weiteren (etwa 12, 17, 40, 666) besondere Bedeutung zugewiesen nach einem vorderasiatischen (jesidischen) Mythos entstanden durch die Vereinigung von Adam und Eva insgesamt 72 verschiedengeschlechtliche Zwillingspaare, die so zu den Vorfahren aller nicht-jesidischen Völker wurden. (Die Jesiden dagegen stammen nach diesem Mythos nur von Adam ab!)
	1. Problembeschreibungen 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 die Narzißzahlen begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Basiswissen der Informatik Wissen für Fortgeschrittene der Informatik Informatik-Profi-Wissen
	Quellen: LOG IN - Heft 146/147 (2007) Seite 75

1. Problembeschreibungen

	Was hat es nun mit der 153 auf sich? Im letzten Kapitel des Johannes-Evangeliums heißt es dazu (Joh. 21-11): „Als sie nun ans Land stiegen, sahen sie ein Kohlenfeuer und Fische darauf und Brot. Spricht Jesus zu ihnen: Bringt von den Fischen, die ihr jetzt gefangen habt! Simon Petrus stieg hinein und zog das Netz an Land, voll großer Fische, hundertdreiundfünfzig. Und obwohl es so viele waren, zeriss doch das Netz nicht." Wie kommt der Autor des Evangeliums zu dieser Zahl? Offenbar steht sie aufgrund mathematischer Operationen mit anderen numerologisch wichtigen Zahlen in Beziehung. Der Heilige Augustinus erklärt sie wie folgt: 153 = (3 - 3) - (7 + 10) und „damit ist klargestellt, dass die Gläubigen in der Kraft des siebenfältigen Geistes die zehn Gebote halten". Die pythagoräische Numerologie dagegen schätzt an 153 die Eigenschaft, Dreieckszahl zu sein: d.h.153=1+2+3+...+ 17, wobei die „heilige" 17 als Anzahl der Summanden auftritt. Im Folgenden wird 153 als sich selbst reproduzierende Zahl charakterisiert, damit ist die Eigenschaft 13 + 53 + 33 = 153 gemeint. In Worten: Bildet man die kubische Quersumme, d. h. die Summe der dritten Potenzen der Ziffern der Zahl, so ergibt sich die Zahl selbst.
	153 als sich selbst reproduzierende Zahl: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 = 153 ;-)
	Aufgabe 1: Es ist 13 + 53 + 33 = 153, 163 + 503 + 333 = 165033, 1663 + 5003 + 3333 = 166500333. Wie geht es weiter, wie lautet das Bildungsgesetz?
	Aufgabe 2: Bildet man die kubische Quersumme einer beliebigen natürlichen Zahl und wiederholt diese Operation, so kann sich unter bestimmten Bedingungen die Zahl 153 als Grenzwert (oder: Fixpunkt) ergeben. Beispiel: 459 --+ 918 1242 -~ 81 -~ 513 --) 153. Untersuchen Sie diesen Prozess (Existenz eines Grenzwerts oder Zyklus, Anzahl der Schritte bis zum Erreichen des Grenzwerts bzw. Zyklus).
	Eine n-stellige natürliche Zahl (n >_ 3) mit der Eigenschaft, dass ihre n-fache Potenzquersumme, also die Summe der n-ten Potenzen ihrer Ziffern, mit der Zahl selbst übereinstimmt, wird in der Literatur als Narziss-Zahl (franz.: nombre narcissique) bezeichnet. Beispiele: 1634 = 14 + 64 + 34 + 44, 54748 = 55 + 45 + 75 + 45 + 85.
	Aufgabe 3: Zeigen Sie mit Computerhilfe: (a) Es gibt genau vier dreistellige Narziss-Zahlen (eine davon ist 153). (b) Finden Sie Narziss-Zahlen für n>3.
	die Dreieckszahlen die dreistelligen Narzißzahlen heißen auch Dreieckszahlen - lustigerweise gibt's davon vier ;-)
	Aufgabe 4: Verallgemeinern Sie Aufgabe 2 auf n-fache Potenzquersummen! (Dabei muss die Anzahl der Stellen der Zahl nicht mit dem Exponenten n übereinstimmen.)

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

	Schnell erreichen wir mit dieser Problemstellung das Ende der verfügbaren Datengrößen (auch Extended-Typen) und die Aufgabe ist bereits bei 10 Stellen extrem zeitkomplex. Das liegt definitiv einfach am gigantischen Rechenaufwand, welcher zum Testen jeder einzelnen Zahl unternommen werden muss. Zudem existieren keinerlei bekannte Vereichfachungs- und/oder intelligente Auslass-Operationen - es muss schlichtweg jede Zahl nach gleichem Muster untersucht werden
	Das Ergebnis: Aus dem Programm erhält man eine Liste Narziss-Zahlen und wer diese nicht glaubt darf nachrechnen. Hier ist meine vorläufige Liste (wird erweitert, wenn das Programm neue Zahlen ausspuckt). unechte Narzissen: 0 1 echte Narzissen (diese enthalten die Dreieckszahlen - das sind die dreistelligen Narzissen): 153 370 371 407 1.634 8.208 9.474 54.748 92.727 93.084 548.834 1.741.725 4.210.818 9.800.817 9.926.315 24.678.050 24.678.051 88.593.477 146.511.208 472.335.975 534.494.836 912.985.153 4.679.307.774 (Berechnungsdauer für die 10-stelligen Narziß-Zahlen von 1000000000 bis 9999999999: 12 Stunden, 31 Minuten und 51 Sekunden) 32.164.049.650 32.164.049.651 40.028.394.225 (Berechnungsdauer für die 11-stelligen Narziß-Zahlen von 10000000000 bis 40999999999: 48 Stunden, 2 Minuten und 9 Sekunden) - danach folgen oberhalb 40999999999 mit einer Rechenzeit von rund 5 Tagen auf einer 266 MHz-Maschine: 42.678.290.603 44.708.635.679 49.388.550.606 dies entspricht jetzt schon einmal: neunundvierzig Milliarden dreihundertachtundachtzig Millionen fünfhundertfünfzig Tausend sechhundertundsechs   die Komplexität eines Problems & Komplexitätsklassen
	wir rechnen für Sie weiter ;-) die Anzahl n, welche wir untersuchen wird aber zunehmend zeitkomplex, da die Anzahl der zu untersuchenden Zahlen 2n beträgt - n nur um eins vergrößert, zieht sofort eine Verdoppelung der Rechenzeit nach sich!!!

3. Lösungsalgorithmus

	Das Programm berechnet Narziss-Zahlen von der minimalen bis zur maximalen Länge der Zahlen, die eingegeben ist. Dazu wird einfach jede Zahl probiert und die, bei denen es funktioniert werden ausgegeben. ACHTUNG! Das Programm läuft bereits bei achtstelligen Zahlen extrem lange!!! Das Programm ist auf 12 (bzw. 19 Stellen ab Version 3.0) begrenzt, aber ich würde schon niemandem mehr als 10 Stellen empfehlen.
	Narziss-Zahlen (von mir auch liebevoll "Narzissen" genannt) sind ganze Zahlen, die sich durch keine Bildungsvorschrift bilden lassen (sind also keine normale Zahlenfolge). Somit weisen sie Eigenschaften der Primzahlen auf. Definiert sind die Zahlen wie folgt: Eine Zahl wird Narziss-Zahl genannt, wenn die Summe aller Potenzen der Ziffern der Zahl mit der Länge der Zahl als Exponent wieder die Zahl ergibt. Beispiel: 153: 1^3+5^3+3^3=1+125+27=153 => 153 ist eine dreistellige Narziss-Zahl Gegenbeispiel: 12345: 1^5+2^5+3^5+4^5+5^5=1+32+243+1024+3125= 4425 < > 12345 => 12345 ist keine Narziss-Zahl Wie viele Narziss-Zahlen gibt es aber nun? Diese Frage ist unbeantwortet, allerdings vermutet man stark, dass es unendlich viele sind. Weiterhin ist ungeklärt, ob die Anzahl der Narziss-Zahlen mit Zunehmender Länge der Zahl stark zunimmt oder ob es wenige bleiben.
	Das Ergebnis: Aus dem Programm erhält man eine Liste Narziss-Zahlen und wer diese nicht glaubt darf nachrechnen. Hier ist meine vorläufige Liste (wird erweitert, wenn das Programm neue Zahlen ausspuckt). unechte Narzissen: 0 1 echte Narzissen: 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153 4679307774 (Berechnungsdauer für die 10-stelligen Zahlen von 1000000000 bis 9999999999: 12 Stunden, 31 Minuten und 51 Sekunden) 32164049650 32164049651 40028394225 (Berechnungsdauer für die 11-stelligen Zahlen von 10000000000 bis 40999999999: 48 Stunden, 2 Minuten und 9 Sekunden) 42678290603 44708635679 49388550606 Zahlen untersucht bis 50999999999

4. Programmvorschläge

	Vom Informatikkurs der Jahrgangsstufe 12 des Schuljahres 2007/08 wurden per Projektarbeit einige solcher Algorithmen erstellt und werden hier nun zusammengefasst sowie präsentiert. Besonders interessante Lösungen kamen aus dieser Gruppe oftmals von Johannes, Eric aber auch von André.
	Version 1.0 (schnellste Berechnung, bis 7 Stellen akzeptabel): Das Programm kann Narziss-Zahlen ausrechnen, allerdings nur bis 9 Stellen, da 10 Stellen bereits Delphis Variablen sprengen. Außerdem muss man den Rechner nach der Berechnung noch an lassen, da die Werte nur in eine ListBox geschrieben werden. Programm zur Ermittlung der Narziss-Zahlen Programm zur Ermittlung der Narziss-Zahlen Programm zur Ermittlung der Narziss-Zahlen
	Version 3.0 (langsamste Berechnung, gut für viele Stellen, da es die Ergebnisse und die Statistik in eine Textdatei schreibt): Das Abspeichern ist noch einmal überarbeitet, d.h. das Programm fragt vor dem Überschreiben einer Textdatei noch einmal nach. Außerdem ist das Problem mit dem begrenzten Zahlenbereich gelöst. Das Programm verkraftet jetzt 19-stellige Zahlen. Außerdem sind noch Änderungen betreffs der Oberfläche und dem Umgang mit großer Mächtigkeit der Zahlen gemacht worden, d.h. man kann ab einer gewissen Zahl starten und das Programm in Schritten zu ca. 14 bis 20 Stunden (bei 1,5 GHz) arbeiten lassen. ACHTUNG!!!! Tests ergaben: auf einem 266 MHz-Rechner dauert die Berechnung eines Schrittes ca. 5 Tage. Programm zur Ermittlung auch großer Narziss-Zahlen - extrem laufzeitkomplex Programm zur Ermittlung auch großer Narziss-Zahlen - extrem laufzeitkomplex Programm zur Ermittlung auch großer Narziss-Zahlen - extrem laufzeitkomplex

5. Zusammenfassung

	Auswertung: An diesem Problem kann man sehr gut die Zeitkomplexität erklären. Aus mehreren Durchläufen des Programms ergaben sich folgendes Muster (berechnet wurde immer ab 3 Stellen bis zur jeweiligen Stellenzahl): Stellenanzahl benötigte Rechenzeit 3 0 4 0 5 0 6 3 7 36 8 407 9 4915 10 45111 10,4 (11 Stellen nicht vollständig) 172929 Laufzeitkomplexität in Abhängigkeit der Stellenzahl

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 die befreundeten Zahlen das Autoquadratzahlenproblem die Schmidtzahlen Pythagoräische Tripel Ulam-Spirale die Polynomzahlen Pascal-Zahlen 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

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 SUDOKU The Busy Beaver-Problem Greedy Algorithm
	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 im September 2007