Die Kaprekar- oder die 6174er-Funktion

Letztmalig dran rumgefummelt: 13.06.08 17:08:29

	... oder auch: Kaprekar-Algorithmus. Beschrieben wird ein Zahlenphänomen, nach welchem von einer beliebigen vierstelligen Zahl nach mehreren (maximal sieben!) Wiederholungen sich immer die Zahl 6174 ergibt. Dazu ist von der vierstelligen Zahl (nicht vierstellige Werte sind durch Anfügen von Vornullen vierstellig zu machen) immer die jeweils größtmögliche  sowie die kleinstmögliche zu bilden und als Absolutwert im Ergebnis voneinander zu substrahieren.
	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 den Kaprekar-Algorithmus Basiswissen der Informatik Wissen für Fortgeschrittene der Informatik Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???

1. Problembeschreibung

	Das eigentliche Problem ist nicht das Feststellen der Kaprekartiefe - weder ist der Algorithmus komplex, noch ist das Problem mächtig. Wenn man das mit dem Taschenrechner überprüft, dauert's vielleicht etwas lange, aber lösbar isses innerhalb 'ner viertel Sunde für praktisch jede Zahl der Teilnehmermenge (man könnte auch Wertebereich sagen, aber ich hasse mathematische Begriffe)! Der Kern liegt eigentlich eher in der Ermittlung einer Formel und/oder eines Algorithmus, welcher(s) beschreibt, in welcher Folge und Abstand welche Kaprekartiefe gilt.
	die Kaprekartiefe liegt im Bereich von 0 bis 7 - dabei ist sie nur bei der Zahl 6174 selbst gleich 0, sonst mindestens 1
	nimm eine beliebige vierstellige Zahl, deren einzelne Stellen nicht alle gleich sein dürfen (1111, 2222, ... , 9999 entfallen also)
	nicht vierstellige Zahlen werden durch Auffüllen mit Vornullen vierstellig gemacht (aus 24 wird also 0024)
	bilde die die größtmögliche mit den vier Ziffern darstellbare Zahl (aus 0024 wird dann 4200)
	bilde die die kleinstmögliche mit den vier Ziffern darstellbare Zahl (0024 bleibt bei 0024)
	ermittle die Differenz zischen größtmöglicher und kleinstmöglicher Zahl
	wiederhole diese Schritte - es ergibt sich nach maximal sieben Wiederholungen 6174 - die Kaprekar-Zahl
	... und weil das ja klappen muss, probieren wir das gleich mal für die 24 ;-)
	größte darstellbare Zahl: 4200 - kleinste darstellbare Zahl: 0024 = 4176     Minus Ist gleich sieht mit 4176 schon ziemlich gut aus, ist aber nicht 6174 ;-) erreicht haben wir derzeit die Kaprekartiefe 1 größte darstellbare Zahl: 7641 - kleinste darstellbare Zahl: 1467 = 6174     Minus Ist gleich   Bing - 6174 erreicht haben wir derzeit die Kaprekartiefe 2 - und das war's auch schon für die 24 (oder was denkt Ihr, warum ich nicht die 25 (mit 'ner Kaprekartiefe von 7) genommen hab (gut - optimal wär' die 6174 gewesen!))?
	ab der Zahl gibt es keine neue Lösung mehr - das ist ja das Phantastische

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

	Unter Annahme der Tatsache, dass wir nicht die Kaprekartiefe, sondern die Regelmäßigkeit der Wiederkehr der einzelnen Werte selbiger suchen, fällt die Aufgabe heute typischerweise in den Bereich der nicht entscheidbaren Probleme. Und diese Beschreibung selbst zu finden, dürfte dann schon in die Klasse der komplexen Probleme fallen.

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.
	Kaprekar-Algorithmus von Johannes Uhlig vom Juni 2006 Abbildung für Kaprekarzahl 27 - und hier der Lösungsalgorithmus mit Quelltext asl ZIP-Archiv

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 die Perfect Numbers die befreundeten Zahlen das 153-Problem - Narziß-Zahlen das Autoquadratzahlenproblem die Schmidtzahlen   Pythagoräische Tripel Ulam-Spirale die Polynomzahlen Pascal-Zahlen die Goldbach-Vermutung das Palindrom-Spiegelsummen-Problem
	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 die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rucksackproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-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 im April 2003