Die vollkommenen oder perfekten Zahlen

Letztmalig dran rumgefummelt: 06.09.26 20:42:41

	Eine natürliche Zahl wird vollkommene Zahl (auch perfekte Zahl) genannt, wenn sie genauso groß ist wie die Summe ihrer positiven echten Teiler (d. h. aller Teiler außer sich selbst). Ist diese Summe der Teiler kleiner als die Zahl selbst, heißt die Zahl defizient. Ist die Teilersumme dagegen größer, so spricht man von einer abundanten Zahl.
	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 Logo für die Perfect Numbers begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: LOG IN - Heft 5/99 (1999) Seite 71/72

1. Problembeschreibung

Bis zum Oktober 2024 waren 52 Mersenne-Primzahlen bekannt; und zwar für folgende Exponenten k:  2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1.279, 2.203, 2.281, 3.217, 4.253, 4.423, 9.689, 9.941, 11.213, 19.937, 21.701, 23.209, 44.497, 86.243, 110.503, 132.049, 216.091, 756.839, 859.433, 1.257.787, 1.398.269, 2.976.221, 3.021.377, 6.972.593, 13.466.917, 20.996.011, 24.036.583, 25.964.951, 30.402.457, 32.582.657, 37.156.667, 42.643.801, 43.112.609, 57.885.161, 74.207.281, 77.232.917, 82.589.933, 136.279.841..

Problembeschreibung historisch und modern

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

Euklid bewies, dass 2n - 1(2n - 1) immer dann eine vollkommene Zahl ist, wenn 2n − 1 eine Primzahl ist, dies sind die so genannten Mersenne-Primzahlen. Fast 2000 Jahre später konnte Leonhard Euler beweisen, dass auf diese Weise alle geraden vollkommenen Zahlen erzeugt werden können. Es ist unbekannt, ob es unendlich viele vollkommene Zahlen gibt. Zudem ist es unbekannt, ob es auch ungerade vollkommene Zahlen gibt. Man weiß jedoch, dass eine solche Zahl, wenn sie existiert, größer als 10500 ist und mindestens 8 (bzw. 11, wenn die Zahl nicht durch 3 teilbar ist) verschiedene Primteiler hat.

Die ersten 10 vollkommenen Zahlen sind: 6 28 496 8.128 33.550.336 8.589.869.056 137.438.691.328 2.305.843.008.139.952.128 2.658.455.991.569.831.744.654.692.615.953.842.176 191.561.942.608.236.107.294.793.378.084.303.638.130.997.321.548.169.216

3. Lösungsalgorithmus

Grundsätzlich erledigen wir beim Ermitteln der Perfekten Zahlen genau das, wodurch sie selbst definiert sind. Testzahl hernehmen, Untersuchungszahl auf Null setzen, alle Teiler außer der Zahl selbst such und immer, wenn ein solcher gefunden wurde, aufaddieren. Abschließend wird diese Summe mit der Testzahl verglich und stimmen sie überein, haben wir eine perfekte Zahl gefunden. Nur extrem laufzeitintensiv ist diese Vorgehensweise.

4. Programmvorschläge

	Hier nun eine erste Lösungsvariante, welche nach genau dem Algorithmus arbeitet, wie er unter Drittens beschrieben wurde. Deshalb Vorsicht mit großen Zahlenräumen - ich such noch nach einer hinreichend schnellen Testmaschine, welche auch in der Lage ist, diese Dimension an Operationen in sinnvoller zeit abzufangen.
	Programm zur Bestimmung der perfekten Zahlen in kleinen Räumen ZIP-Archiv im Delphi 6.0-Format zum Programm ausfürhbares  Programm

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 ;-)

7. Links zum Thema

	http://de.wikipedia.org/wiki/Vollkommene_Zahl

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-Damen-Problem das Cliquenproblem das Dominoproblem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Wortproblem das Hamiltonproblem das K-Farben-Problem das Flaggenproblem das Halteproblem das Königsberger Brückenproblem das Philosophenproblem das Teilsummensummenproblem das Post'sche Korrespondenz-Problem das Rucksackprolem (Knapsackproblem) das Rundreiseproblem - aber: beachte die Mächtigkeit! das Springerproblem die Türme von Hanoi - mit hoher Anzahl von Scheiben wird das Problem praktisch nicht lösbar - 64 ist bereits enorm hoch das Knotenüberdeckungsproblem The Busy Beaver-Problem das Spannbaumproblem der Maze-Running-Algorithmus das Schachspiel Greedy Algorithm das Maximalflussproblem das Syntheseproblem   das k-Next-Neighbor-Problem   Schwarmintelligenz ... fehlererkennende Algorithmen -  ISBN-Nummer das Binärbaumproblem geometrischen Probleme Dijkstra-Algorithmus Fermat'sches Problem FERMAT's letzter Satz   ZIP-Algorithmus   Bresenham-Algorithmus   der Huffman-Code LZW-Kompression   Quadratsummen-Problem   die glücklichen & traurigen Zahlen   Smarandache-Wellin-Zahlen der austarierte Baum   Trunkierbare Primzahlen   FERMAT'scher Großer Satz   Eulerkreis   Lauflängen-Codierung   Zeichenkettenabgleich
	die Primzahlsuche die Primzahl-Faktorierung Miller-Rabin-Test   der Fluch des Pharao-Algorithmus die Chiffrierung ohne Schlüssel das Teilerproblem Die Sache mit dem Wüstenfit (gefällt mir zu gut) Die Magischen Quadrate - hier beschrieben von Stefan Hecker in einer Belegarbeit aus dem Schuljahr 2001/02 das Chinesische Kisten- oder chinas Postmen-Problem das Labyrinth das PASCAL'sche Dreieck SUDOKU
	einfache aber rechenintensive Spielereien mit Zahlen all den folgenden Problemstellungen ist gemein, dass sie extrem einfach zu beschreiben sind - einzelne Lösungen oder gar alle bzw. mindestens viele zu finden, ist jedoch u. U. extrem zeitkomplex - auch schnelle Computer können daran sehr lange tüffteln. - wer's nicht glaubt, probiert's aus, aber vorab die Randbedingungen gut durchlesen - teilweise gibt's extrem lange Wartezeiten und die Lösung erscheint evtl. in einer Woche, wenn überhaupt Selbst, wenn wir die mitunter große Laufzeit akzeptieren können, stoßen wir teilweise recht schnell an die Realisierbarkeit durch die verfügbaren Datentypen - eine Million ist hier ein eher kleiner Wert - dies zeigen uns sehr deutlich die Perfect Numbers die Primzahl-Zwillingssuche die Primzahl-Palindrome der Kaprekar Algorithmus die befreundeten Zahlen Pythagoräische Tripel die Schmidtzahlen das Autoquadratzahlenproblem Ulam-Spirale die Polynomzahlen Pascal-Zahlen die Goldbach-Vermutung das 153-Problem - Narziß-Zahlen   die Pólya-Vermutung Zahlensystem-Umechner ...als Startbare Datei Software zur Veranschaulichung der Zahlenumrechung das Palindrom-Spiegelsummen-Problem die ABC-Vermutung

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost am 30. Mai 2008