Das Autoquadratzahlenproblem

Das Autoquadratzahlenproblem oder auch die Autoquadzahlen

Letztmalig dran rumgefummelt: 15.05.23 01:21:13

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 Autoquadzahlen. 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 Literatur
7. Linkliste zum Thema
8. Verwandte Themen

Probleme & Problemlösungsverfahren

das hat auch viel mit Problemlösungsstrategien zu tun

Logo für das Chinesische Kisten-Problem

begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-)

Informatik-Profi-Wissen

Quellen:
LOG IN - Heft 146/147 (2007) Seite 48 ff.

The Chinese-Box

1. Problembeschreibung

Finde alle natürlichen Zahlen n mit der Eigenschaft, dass ihr Quadrat n² auf n endet.

n n²

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 n²

5 25

25 625

625 390625

90625 8212890625

890625 793212890625

2890625 8355712890625

12890625 166168212890625

212890625 45322418212890625

die ersten 10 Fünfer-Autoquadzahlen

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 2¹⁰ 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 Biglnter ü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

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 Literatur

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

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)

	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 2¹⁰ 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 Biglnter ü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.