Das Autoquadratzahlenproblem oder auch die Autoquadzahlen

Letztmalig dran rumgefummelt: 11.06.08 19:34:39

	Finde alle natürlichen Zahlen mit der Eigenschaft, dass sie auf ihre Quadratwurzel enden. Beispiel: Wegen Quadratwurzel 5776 = 76 ist 5776 eine der gesuchten Zahlen. Wir verschaffen uns - mittels Papier und Bleistift, Taschenrechner usw. - einige einfache Spezialfälle (Beispiele): Für die Zahlen n von 0 bis 9 lauten die Paare (n, n²) wie folgt: (0, 0), (1, 1). (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49), (8, 64), (9, 81). Die Zahlen 0, 1, 5 und 6 sind also Autoquadratzahlen. Damit haben wir bereits vier Lösungen gefunden. lm Bereich 10 <= n < 99 erhalten wir die Paare (25, 625) und (76, 5776).
	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 das hat auch viel mit Problemlösungsstrategien zu tun Logo für das Autoquadratzahlenproblem begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: LOG IN - Heft 146/147 (2007) Seite 48 ff.

1. Problembeschreibung

	Finde alle natürlichen Zahlen n mit der Eigenschaft, dass ihr Quadrat n2 auf n endet. Dummerweise werden zumindest die zutreffenden Quadrate sehr schnell so groß, dass diese mühelos das darstellbare Datentypenspektrum zumindest im ganzzahligen Bereich überschreiten.
	n n2 1 1 5 25 6 36 25 625 76 5776 376 141376 625 390625 9376 87909376 90625 8212890625 109376 11963109376 890625 793212890625 2890625 8355712890625 7109376 50543227109376 12890625 166168212890625 87109376 7588043387109376 212890625 45322418212890625 die ersten 16 Autoquadzahlen
	n n2 5 25 25 625 625 390625 90625 8212890625 890625 793212890625 2890625 8355712890625 12890625 166168212890625 212890625 45322418212890625 die ersten 10 Fünfer-Autoquadzahlen
	1      1 5      25 6      36 25      625 76      5776 376      141376 625      390625 9376      87909376 90625      8212890625 109376      11963109376 890625      793212890625 2890625      8355712890625 7109376      50543227109376 12890625      166168212890625 87109376      7588043387109376 212890625      45322418212890625 787109376      619541169787109376 1787109376      3193759921787109376 8212890625      67451572418212890625 18212890625      331709384918212890625 81787109376      6689131260081787109376 918212890625      843114912509918212890625 9918212890625      98370946943759918212890625 59918212890625      3590192236006259918212890625 259918212890625      67557477392256259918212890625    hat Eric Kreller mit seinem Programm berechnet ;-)

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.
	Programm für weitere Spezialfälle Wir wollen nun ein Programm schreiben, das alle dreistelligen Autoquadzahlen ermittelt. Hier stellt sich die Frage, wie man die letzten drei Ziffern einer Zahl herausgreift. Aus dem Mathematikunterricht wissen wir. dass sich die letzten n Ziffern als Rest bei Division durch 10° gewinnen lassen. Damit können wir ein erstes JAVA-Programm aufschreiben: public class Autoquad public static void main (String[] xy) for (long n = 100; n < 1000; n++) long q = n * n; if (q % 1000 == n) System.out.println(" " + n + , " + q); } // Ende for Ende main Ende Autoquad Es liefert uns die Zahlenpaare (376, 141376) und (625, 390625), also die Autoquadzahlen 376 und 625.
	Programm-Modifikation für noch mehr einfache Fälle Um auch die ein- und die zweistelligen Zahlen zu untersuchen, ändern wir in obigem Programm die Zählschleife zum einen so, dass sie von 1 bis 9, und zum anderen so, dass sie von 10 bis 99 läuft. Im ersten Fall rechnen wir modulo 10, im zweiten modulo 100. Damit erhalten wir die Zahlenpaare (1, 1), (5, 25), (6, 36). (25. 625) und (76, 5776). Nun kennen wir also - außer dem trivialen Fall 0 - die ersten sieben Autoquadzahlen, nämlich 1, 5, 6, 25, 76, 376 und 625.
	Verallgemeinerung zum Erfassen aller bisherigen Lösungen Wir entwickeln nun ein Programm, das die verschiedenen Bereiche 1..9, 10..99, 100..999 usw. der Reihe nach durchläuft. Diesem Zweck dient eine äußere Schleife, welche die genannten Potenzen von 10 erzeugt. Das folgende Programm liefert Bild 4, also zusätzlich die B. bis 16. Autoquadzahl. public class Autoquad public static void main (String[] xy) long potenz = 1; while (potenz < 10000000) long modul = 10 * potenz; for (long n = potenz; n < modul ; n++) long q = n * n; if (q % modul == n) System.out.println(" " + n + , " + q); } // Ende for potenz = modul; } // Ende while Ende main Ende Autoquad
	Hier stoßen wir nun an die Grenze des Rechnens mit „langen" ganzen Zahlen (Datentyp long). Sie lässt sich durch Übergang zu Zahlen vom Typ 64lnt überwinden. Doch wird nun die (Länge der) Rechenzeit zum Problem. Damit ist der Augenblick gekommen, unser Denkvermögen einzusetzen, d. h. die Aufmerksamkeit weg vom Programmieren auf die Entwicklung eines etwas intelligenteren Algorithmus zu richten. Bisher sind wir ja mit „Brachialgewalt" vorgegangen, indem wir jede einzelne Zahl darauf prüften, ob sie autoquadratisch sei: Die Anzahl der zu prüfenden Zahlen und damit auch die Rechenzeit stieg mit jeder zusätzlichen Stelle auf das Zehnfache. Wir halten fest: Ein Programm, bei dem die Rechenzeit mit der Problemgröße exponentiell wächst, ist für die Praxis wertlos. 6. Verbesserung des Algorithmus durch mathematische Analyse Schauen wir uns die bisher ermittelten Autoquadzahlen etwas genauer an! Es fällt auf, dass aus einer bereits ermittelten Autoquadzahl einfach durch Erweiterung eine weitere gewonnen werden kann, d. h. dadurch, dass wir vorne eine Ziffer X oder XO anfügen. Beispielsweise wird aus 76 die neue Autoquadzahl 376 oder aus 625 wird 90625. Entscheidend dabei ist: Auf diese Weise gewinnen wir alle Autoquadzahlen. Denn es gilt der Satz 1: Zu jeder Autoquadzahl > 10 gibt es eine (kleinere) Autoquadzahl, deren Erweiterung sie ist. Wir verwenden ihn zunächst in folgender Form: Lässt man in einer Autoquadzahl die erste Ziffer weg, so erhält man wieder eine. Satz 1 zeigt, dass eine Autoquadzahl stets auf eine kleinere reduziert werden kann. Da 5 und 6 die einzigen (nichttrivialen) einstelligen Autoquadzahlen sind, müssen alle anderen auf eine dieser beiden Ziffern enden. Der Satz besagt weiter, dass alle größeren Autoquadzahlen durch Erweiterung aus kleineren gebildet werden können, d. h. durch Voranstellen neuer Ziffern. Dass eine solche Erweiterung immer möglich ist, geht aus folgendem Satz hervor: Satz 2: Jede Autoquadzahl kann durch Voranstellen einer eindeutig bestimmten Ziffer zu einer größeren Autoquadzahl erweitert werden. Der Beweis (siehe Scheuch, 2003, S. 40) liefert einen Algorithmus zur Bestimmung der Erweiterungsziffer. Ist z„ die Anzahl der Ziffern der natürlichen Zahl n, so gilt für die auf 5 endenden Autoquadzahlen: Wenn die (z„ + 1)-te Ziffer von n2 ungleich null ist, so wird die neue Autoquadzahl durch die ersten z„ + 1 Ziffern von n2 gebildet, andernfalls durch die ersten zn + 2 Ziffern - und zwar jeweils von rechts her gezählt. Sei beispielsweise n = 90625, dann ist zn = 5 und n2 = 8212890625; die sechste Ziffer von rechts ist 8, also ungleich null. Somit ist die nächste Fünfer-Autoquadzahl 890625 (siehe Bild 4, vorige Seite). Für die Sechserzahlen gilt: Die neue Autoquadzahl wird durch die ersten zn + 1 Ziffern von n2 gebildet, wobei die (Zn + 1)-te Ziffer durch ihr Zehnerkomplement zu ersetzen ist - und zwar jeweils von rechts her gezählt. Sei beispielsweise n = 9376, dann ist z„ = 4 und n2 = 879_09376; das Zehnerkomplement der fünften Ziffer von rechts ist 10 - 0 = 10, also ist die nächste Sechser-Autoquadzahl 109376 (siehe Bild 4, vorige Seite). Das folgende Programm liefert die Folge der auf 5 endenden Autoquadzahlen beliebiger Länge (Bild 5), d. h. soweit der Speicherplatz reicht: import java.math.*; public class Autoquad { public static void main (String[] xy) String a = "5", for (int i = 0; i < 10; i++) BigInteger n = new BigInteger(a); String q = n.multiply(n).toString(); System.out.println(" " + a + q); int zn = a.length(); int zq = q.length(); char ziffer = q.charAt(zq - zn - 1); a = ziffer + a; if (ziffer == '0') a = q.charAt(zq - zn - 2) + a; // Ende for // Ende main // Ende Autoquad Wir ziehen folgendes Fazit: Wenn du ein Programm geschrieben, getestet, von Fehlern befreit und zum Laufen gebracht hast, so denke noch einmal über das Problem nach. Häufig wirst du eine bessere Lösungsstrategie entdecken. Das meinte Pölya, wenn er davon sprach, dass sich auf diese Weise das Wissen und die Fähigkeit zum Problemlösen erweitern lassen.

3. Lösungsalgorithmus

Wie oben beschrieben kann ich zwei Instanzen von wohlgemerkt korrekten Lösungen verfolgen: ich nehme die Billigvariante und berechne von einer jeden Zahl deren Quadrat. Dieses zerlege ich aus einem String in seine Character und vergleiche von rechts beginnend mit der Basiszahl - stimmt dieser String wieder überein, so habe ich eine Autoquadratzahl ermittelt. Intelligenter benutze ich dazu allerdings bereits als richtig erkannte Muster und verwende nur Basiszahlen, welche auf "5" oder "6" enden. Das allerdings ist risikobehaftet, denn nu bleiben mit Sicherheit 'ne Menge Zahlen außen vor. Wer garantiert, dass es trotz aller Wahrscheinlichkeiten in den großen Basen nicht doch noch mindestens eine zahl gibt, welche von dieser Konstellation abweicht?

4. Programmvorschläge

	Es gab einiges an Ideen - schlussendlich habe ich mich für André Neuberts Programmversion entschieden, wenngleich die Zahlen nicht besonders groß sind. Bei Erics Programmierung mit Dot.Net geht das dann auch mit wesentlich größeren Zahlen.
	Programm zur Ermittlung kleiner Autoquadrat-Zahlen Programm zur Ermittlung auch großer Narziss-Zahlen - extrem laufzeitkomplex Programm zur Ermittlung auch großer Narziss-Zahlen - extrem laufzeitkomplex
	diese Variante läuft nut nur bei einer vorab installierten Version von Dot.Net Programm zur Ermittlung auch sehr großer Autoquadrat-Zahlen Programm zur Ermittlung auch großer Narziss-Zahlen - extrem laufzeitkomplex Programm zur Ermittlung auch großer Narziss-Zahlen - extrem laufzeitkomplex

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 die befreundeten Zahlen das 153-Problem - Narziß-Zahlen 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

	http://www.mathematische-basteleien.de/kaprekarzahl.htm

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 Ros am 24. Dezember 2007