Kaprekar-Konstanten und Kaprekar-Zahlen
Auf den indischen Mathematiker Dattaraya Ramchandra Kaprekar (1905 - 1986)
gehen u. a. zwei interessante Probleme der Zahlentheorie
zurück. Hier wir das Problem der so genannten
Kaprekar-Konstanten behandelt, den
Kaprekar-Zahlen ist eine
eigene Seite gewidmet.
Das Phänomen, das mit den Kaprekar-Konstanten verknüpft ist,
wurde im Jahre 1949 zunächst für vierstellige Zahlen formuliert:
Satz von Kaprekar:
Man nehme eine beliebige vierziffrige Zahl (z. B.: 2195),
bei der nicht alle vier Ziffern gleich sind (also nicht
1111, 2222, 3333, ...) und ordne die Ziffern der Größe nach
absteigend (im Beispiel: 9521). Von der entstehenden Zahl
subtrahiere man die Zahl, die bei aufsteigender Anordnung der
Ziffern entsteht (im Beispiel: 1259). Mit der entstandenen
neuen Zahl (im Beispiel: 9521 − 1259 = 8262)
wird der Prozess wiederholt.
Nach einigen Schritten landet man immer bei der Zahl 6174
("Kaprekar-Konstante" für vierstellige Zahlen),
die sich dann bei weitereren Schritten stets selbst reproduziert.
Eine entsprechende Aussage kann für dreiziffrige Zahlen formuliert
werden, für die die Zahl 495 die Kaprekar-Konstante ist.
Für die Startzahl 573 berechnet man zum Beispiel:
753 − 357 = 396 →
963 − 369 = 594 →
954 − 459 = 495 →
954 − 459 = 495 .
Man probiere
die beiden Aussagen mit dem nachstehenden Script aus!
Startzahlen mit beliebiger Ziffernanzahl
Vor der Formulierung weiterer Aussagen werden folgende
Begriffe vereinbart:
- Als Kaprekar-Algorithmus wird die
oben für die vierziffrigen Zahlen formulierte Vorschrift verstanden,
sinngemäß erweitert auf Startzahlen mit n
Ziffern. Als Kaprekar-Folge wird die endliche
Zahlenfolge bezeichnet, die aus einer beliebigen Startzahl
durch wiederholte Anwendung des Kaprekar-Algorithmus entsteht
und endet, wenn ein Element ein zweites Mal auftritt.
- Als n-stellige Kaprekar-Konstante
wird eine Zahl bezeichnet,
die sich bei Anwendung des Kaprekar-Algorithmus sofort
selbst reproduziert (wie die 495 oder die 6174).
Man beachte, dass damit nicht gefordert wird, dass der
Kaprekar-Algorithmus für eine beliebige
n-stellige Startzahl auf diese
(oder eine andere)
n-stellige Kaprekar-Konstante
führen muss.
Folgende Aussagen über Startzahlen mit unterschiedlicher Anzahl
von Ziffern sind möglich:
- Es gibt keine zweistellige Kaprekar-Konstante. Die Anwendung
des Kaprekar-Algorithmus auf zweistellige Startzahlen führt
aber immer auf einen Zyklus mit 5 Zahlen, der sich bei weiterer
Rechnung ständig wiederholen würde:
81 → 63 → 27 → 45 → 9 → 81.
- Für beliebige dreistellige Startzahlen endet der Kaprekar-Algorithmus
immer bei der Kaprekar-Konstanten 495, für beliebige vierstellige
Startzahlen endet der Kaprekar-Algorithmus
immer bei der Kaprekar-Konstanten 6174.
- Es gibt keine fünfstelligen und keine siebenstelligen
Kaprekar-Konstanten.
- Es gibt jeweils mehrere sechs-, acht-, neun- und zehnstellige
Kaprekar-Konstanten:
- 549945 und 631764 (sechsstellig),
- 63317664 und 97508421 (achtstellig),
- 554999445 und 864197532 (neunstellig),
- 6333176664 und 9753086421 und 9975084201 (zehnstellig).
Man beachte, dass diese
Kaprekar-Konstanten sich zwar selbst
reproduzieren (man probiere es mit dem nebenstehenden Script),
aber bei beliebigen Startzahlen der entsprechenden
Länge in der Regel
nicht die Endzahlen der Kaprekar-Folge
sind. In den weitaus meisten Fällen endet die Kaprekar-Folge
(Ausnahmen sind die drei- und vierstelligen Startzahlen)
in einem Zyklus.
Natürlich enden alle Kaprekar-Folgen beliebiger Startzahlen
irgendwann in einem Zyklus, weil es nur eine endliche Menge
möglicher Ergebnisse der Kaprekar-Schritte gibt und sich
zwangsläufig ein Ergebnis irgendwann wiederholt, und damit
beginnt ein Zyklus. Überraschend ist jedoch, wie schnell
das im Allgemeinen passiert. Man probiere es aus: Selbst bei
20-stelligen Startzahlen darf man darauf vertrauen, dass das
Script nach relativ kurzer Zeit ein Ergebnis liefert.
Algorithmen zur Erzeugung von Kaprekar- Konstanten
Eine umfassende und sehr interessante Untersuchung zu diesem Thema wurde mir
von Josef Meiler geliefert. Hier findet man sie als PDF-Datei.