Mathematiker - Sa 17.11.12 21:20
Titel: Ägyptische Zerlegung einer Zahl

---

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

Horst_H - So 18.11.12 17:10

---

Hallo,

Hier [http://www.mathehotline.de/mathe4u/hausaufgaben/messages/4244/358730.html] steht doch etwas dazu dies hier [http://www.mathehotline.de/cgi-bin/mathe4u/hausaufgaben/show.cgi?tpc=4244&post=146938#POST146938].
Am Ende vom Text skizziert Christian_s (Christian_s) eine Lösung, aber die ja nicht der Weisheit letzter Schluß ist, da nur eine Lösung erzeugt wird.

Zitat:

100000=16384+16384+16384+16384+8192+8192+6144+3072+3072+1536+1536+768+768+384+384+192+64+48+32+24+24 +12+12+6+2

Gruß Horst

Mathematiker - So 18.11.12 17:20

---

Hallo Horst_H,

Horst_H hat folgendes geschrieben :

Hier steht doch etwas dazu dies hier [http://www.mathehotline.de/cgi-bin/mathe4u/hausaufgaben/show.cgi?tpc=4244&post=146938#POST146938].

Danke für den Hinweis. Dies kannte ich noch nicht. Mit den C-Texten werde ich wieder Probleme kriegen, aber irgendwie verstehe ich das schon.
Zuerst dachte ich der Christian S. von dort ist auch der Christian S. aus der EE. Beide sind wohl aber verschieden. :lol:

Beste Grüße
Mathematiker