Hallo,
heute mal wieder mit einem algorithmischen Problem, konkret einer ägyptischen Zerlegung einer natürlichen Zahl.
Eine natürliche Zahl n heißt ägyptische Zahl, wenn sie als Summe der Nenner einer Zerlegung der 1 in eine Summe von Stammbrüchen dargestellt werden kann.
Zum Beispiel ist 11 eine ägyptische Zahl, da
1 = 1/2 + 1/3 + 1/6 und 11 = 2 + 3 + 6
ist. Nichtägyptische Zahlen sind zum Beispiel 2, 3, 5, 6, 7, 8, 12, 13, ...
Eine Zahl heißt sogar streng ägyptisch, wenn die Nenner der Stammbruchsumme aller Brüche verschieden sind. 1963 bewies Graham, dass alle natürlichen Zahlen > 77 streng ägyptisch sind.
Ich versuche nun, alle ägyptischen Zerlegungen und insbesondere die strengen zu finden.
So lange die Ausgangszahl nicht größer als 80 wird, ist alles noch gut. Dann steigt aber der Zeitbedarf exponentiell und ist schon für 100 undiskutabel.
Konkret ermittle ich alle möglichen Partitionen (ohne 1) der Zahl und teste, ob die Summe der Reziproken 1 wird. Da die Zahl der Partitionen p(n) nach Ramanujan etwa exp(sqrt(n)) ist, wird deren Wert extrem schnell sehr groß.
Sieht jemand von Euch eine Möglichkeit, das Verfahren zu beschleunigen. Wahrscheinlich braucht man auch eine andere Grundidee.
Als Anhang füge ich meine Lösung an. Danke für Eure Mühe.
Beste Grüße
Mathematiker
Einloggen, um Attachments anzusehen!
_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein