Zahlwort

Zu jeder Zahl kann ermittelt werden, auf wieviele Arten sie als Summe aufein­ander­folgender Prim­zahlen geschrieben werden kann. Und es liegt die Frage auf der Hand, welche die kleinste Zahl zu einer vorge­gebenen Anzahl von Zerle­gungen ist. [1] So kann die 41 auf drei­fache Art als Summe von Prim­zahlen in Folge geschrieben werden, nämlich als 3+5+7+11+13, als 11+13+17 und als 41 allein. Und 41 ist die kleinste Zahl mit dieser Eigen­schaft. Für exakt 1, 2, 3, 4 und 5 Summanden erhält man als kleinste Summe 2, 5, 41, 1151 und 311:

1    2    3              4                      5                   
2    5    41             1151                   311
     2+3  11+13+17       379+383+389            101+103+107
          2+3+5+7+11+13  223+227+229+233+239    53+59+61+67+71
                         7+11+13+...+89+97+101  31+37+41+43+47+53+59
                                                11+13+17...+41+43+47

Darunter ist die Zahl 311 deshalb bemer­kenswert, weil sie mit fünf Zerle­gungen deut­lich kleiner ist als 1151 mit nur vieren.

Das ist zwar keine Eigenschaft mit irgendeinem prak­tischen Nutzen, dennoch aber eine von allge­meiner Bedeutung, daß sie Besuchern aus dem Welt­raum zwar nicht geläufig, aber bekannt sein wird. Das unter­scheidet von irdischen Beliebig­keiten: Der 311 als ameri­kanische Nicht-​Notruf-​Nummer im Gegen­satz zur 911. Dem Anschlag in Madrid (3/11/2004) im Gegen­satz zu dem in New York (9/11/2001). Oder der Verdrei­fachung des 11. Buch­stabens K zu KKK, nicht für „Kinder, Küche, Kirche“ sondern für den Ku Klux Klan.

[1] The On-Line Encyclopedia of Integer Sequences. Anzahl der Zer­legun­gen A054845 einer Zahl und klein­ste Zahl A054859 einer vorge­gebenen Anzahl von Zerle­gungen.

Ich bin kein Mathematikgenie, nein das nicht. Aber sowas ist schön zu lesen.

Viele werden sich weigern, eine Summe aus nur einem Sum­manden als solche anzu­erkennen. Nicht nur für sie gibt es natür­lich auch eine Aufstel­lung [1] der klein­sten Zahlen mit einer vorge­gebener Anzahl echter Zerle­gungen [2]:

1   2         3                       4               5                      
5   36        240                     311             16277
2+3 17+19     113+127                 101+103+107     2297+2309+...+2339+2341
    5+7+11+13 53+59+61+67             53+59+61+67+71  1451+1453+...+1499+1511
              17+19+23+29+31+37+41+43 31+37+...+53+59 1231+1237+...+1303+1307
                                      11+13+...+43+47 359+367+373+...+571+577
                                                      331+337+347+...+557+563

Wieder ist 311 dabei, weil diese Primzahl ja gut auf ihre triviale Zerle­gung ver­zichten kann. Sie hat dann zwar nur noch vier echte Zer­legun­gen statt fünf insge­samt, doch wissen wir bereits, daß alle Zahlen unter­halb von 311 maximal drei Zerlegungen haben, also keine vier und schon gar keine echten.

Anders steht es um die 41. Als Prim­zahl bleiben ihr von den drei Zerle­gungen nur zwei echte. Dadurch erhalten klei­nere Zahlen die Chance auf eben­falls zwei, die als kleinste von der 36 wahr­genom­men wird. Das gleiche Schick­sal erlei­det die 1151. Von den vier Zerle­gungen bleiben drei echte. Aber das schafft die kleinere 240 auch.

[1] Wie auch im Hauptbeitrag ehemals als eine schöne Tabelle mit Umran­dung. Doch eines Tages wurde aus welchem Grunde auch immer <table> einfach entfernt, sobald man nach­edi­tierte.

[2] The On-Line Encyclopedia of Integer Sequences. Anzahl der echten Zer­legun­gen A084143 einer Zahl und klein­ste Zahl A067376 einer vorge­gebenen Anzahl von echten Zerle­gungen.

Hier noch einmal eine Zusammen­stellung der kleinsten Zahlen mit vorge­gebener Anzahl von Zerle­gungen:

n	kleinste Zahl mit genau n Zerlegungen
	alle Zerlegungen zählen	nur echte Zerlegungen zählen
1	2	5
2	5	36
3	41	240
4	1151	311
5	311	16277
6	34421	130638
7	218918	218918
8	3634531	9186778
9	48205429	556259425
10	1798467197	4611108324
11	12941709050	12941709050
12	166400805323	­

Im Mittel sind die Zahlen in der rechten Spalte etwa dreimal so groß wie in der linken, und mit jeder Zeile wachsen sie unge­fähr um den Faktor zehn. Ob das auf bei wesenlich größeren Trefferzahlen als 12 so bleibt, ist zu bezweifeln.

Daß gelegentlich neben­einander zwei gleiche Zahlen stehen (218918) ist durch­aus zu erwarten. Ist die kleinste Zahl mit genau n Zerle­gungen näm­lich zusam­men­gesetzt, ist sie auch die kleinste mit genau n echten Zerlegungen. Ebenso normal sind zwei gleiche Zahlen längs der Diago­nalen (5).

Wahrscheinlich gibt es in den unbe­kannten Tiefen der Fortsetzung der Tabelle noch eine zweite Zahl wie 311, deren Vor­gänger (1151) sogar größer ist. Aber die ist dann sehr groß und interessiert eigentlich nicht mehr.

Eine naheliegende Frage lautet: In welchen Maße wächst die kleinste Zahl mit der Anzahl der vorge­gebe­nen Zerle­gungen? Dazu habe ich einmal die Treffer­dichte überschlagen. Um die Zahl n herum haben die Prim­zahlen einen mitt­leren Abstand von log(n), für die Summen zweier Prim­zahlen ist er 2log(n/2), für die aus dreien 3log(n/3) usw. Summiert man deren Kehr­werte, ergibt sich eine mit wach­sendem n gegen log(2)=0,69 gehende Trefferdichte. Die Verhält­nisse liegen weitgehend unab­hängig von n wie folgt:

r    = log(2)    = 69%  Trefferdichte
p(0) = exp(-r)   = 50%  haben keine Zerlegung
p(1) = r*p(0)    = 35%  haben eine Zerlegung
p(2) = r*p(1)/2  = 12%  haben zwei Zerlegungen
p(3) = r*p(2)/3  =  3%  haben drei Zerlegungen

Das sind die Ergebnisse einer Überschlags­rechnung, die unbe­rück­sichtigt läßt, daß die Treffer nicht wirklich unab­hängig fallen. Sie haben nämlich einen einiger­maßen gleich­blei­benden Abstand vonein­ander. Und vom Sum­manden 2 einmal abgesehen sind Summen mit gerader Summan­denzahl immer gerade und mit ungerader Summan­denzahl immer ungerade. Es ist deshalb nicht selbstver­ständlich, daß schon bei kleinen Zahlen die errech­neten Werte sehr gut getroffen werden:

Das Diagramm erstreckt sich bis zur Zahl 10.000 und gibt die Treffer in Blöcken zu je 100 Zahlen wieder. Wenn dieses Dia­gramm und meine Berech­nungen mich nicht täuschen, sollte die Wahr­schein­lichkeit, daß die kleinste Zahl mit k Zerle­gungen kleiner ist als die mit k-1 Zerle­gungen etwa 1/k sein. Unter­halb von 12 liegt mit 311 bei k=5 die einzige solche Umkehr der Reihen­folge. Im Bereich von 12 bis 100 ist mit zwei weiteren zu rechnen. Vielleicht werden leistungs­fähige Rechner in Haus­halten von Spinnern bald eine davon finden.

Aber zurück zur Eingangs­frage, in welchem Maße die kleinsten Zahlen mit wach­sender Treffer­zahl größer werden. Die Tabelle

n	Zahlen mit genau n Zerlegungen
	kleinste	alle wieviel
1	2	3
2	5	8
3	41	36
4	1.151	208
5	311	1.500
6	34.421	13.000
7	218.918	131.000
8	3.634.531	1.500.000
9	48.205.429	20.000.000
10	1.798.467.197	280.000.000
11	12.941.709.050	4.500.000.000
12	166.400.805.323	78.000.000.000

gibt die bekannten kleinsten Zahlen und dane­ben die zu erwar­tenden Abstände zwischen Zahlen mit der vorge­gebe­nen Treffer­zahl an, sofern die Gesamt­dichte tatsächlich gegen log(2)=0,69 tendiert. Die Tabelle und mein Dia­gramm legen einen etwas kleineren Wert nahe. Und so ent­stehen aus einer Antwort wieder einmal zwei Fragen: Führt genau­ere Rech­nung auf weniger als log(2), und warum werden bei kleinen Zahlen Doppel­treffer bevor­zugt, bleibt also die Zahl der Einzel­treffer deut­lich hinter 35% zurück?

das prinzip der primzahlen
eine minimalisierung in der wiederholung und eine maximalisierung in der streuung von elementen abzählbar unendlicher welten (mengen)

ich habe mich mit primzahlen ein wenig beschäftigt
obige philosophische (arbeitshypo-)these ist mehr oder weniger intuitiver natur

Die erste Schlußfrage meines voran­gehenden Kommen­tares lautete: Warum bleibt die Trefferrate zumindest unterhalb von 10000 deutlich hinter log2=69% zurück und fällt sogar konti­nuierlich ab?

Zur Antwort muß etwas genauer gerechnet werden. Gehe ich weiter­hin davon aus, daß um die Zahl n herum die Summen aus i Prim­zahlen in Folge einen mitt­leren Abstand von i·log(n/i)) haben, ergibt sich eine Gesamt­treffer­quote von

s(n) = 1/logn + 1/(2·log(n/2)) + ... + 1/(k·log(n/k))

worin k so gewählt wird, daß die Summe der ersten k Primzahlen n ergibt. Das ist ungefähr bei

n = (k/2)logk  oder  n = 2√(n/logn)

der Fall und führt letztlich auf die Näherung

s(n) = log2 + (2-loglogn)/logn

Bis n=exp(exp(2)) um 1600 liegt s(n) oberhalb von log2=0,69 und fällt dann bis n=exp(exp(3)) um 500 Milliarden ganz langsam auf etwa 0,64 ab. Erst danach steigt s(n) wieder gegen die Zielwert log2=0,69. Das steht im Einklang mit dem Verlauf der von mir bis n=10000 gezählten Treffer.

Damit ist die Eingangsfrage einigermaßen beantwortet, und ich will diesmal nur eine Folgefrage erwähnen: Warum bleiben die ermittelten Werte hinter den errechneten zurück? Von 1001 bis 2000 zähle ich 676 Treffer, das sind 21 weniger als s(1500)=0,697 erwarten läßt. Von 8001 bis 9000 sind es 659 und damit 12 weniger. Die Abweichung scheint abzunehmen. Doch ist das wirklich der Fall? Ein mir bekanntes Ergebnis [1] spricht dagegen: Bis 260 Milliarden gibt es 5722 Neunfach-Treffer, was nach der Beziehung

5722 / 260.000.000.000 = (s9/9!)e-s

auf eine Trefferrate von s=0,632 schließen läßt. Das sind im Tausenderblock immer noch 13 Treffer weniger als mit der Näherungsformel berechnet.

Und für den einen, der wirklich nachrechnet, sage ich es gleich: Die 2 aus dem Korrekturterm (2-loglogn)/logn ist von mir großzügig gerundet. Sie steht für c(n)+2log2, worin c(n) ausgleicht, was bei der Ersetzung der Summe durch ein Integral verschlappert wird. Naturgemäß liegt dieser Wert für große n in der Nähe der Euler-Mascheroni-Konstante [2]. Ich habe ihn großzügig mit 0,614 angesetzt, um auf 2 zu kommen.

[1] Primepuzzles
[2] γ=0,577...

In meinem letzten Kommentar blieb ich eine Antwort auf die Frage schuldig, warum die wahre Treffer­rate hinter der von mir errech­neten um einige Pro­zente zurück­bleibt. Neben falscher oder unge­nauer Rech­nerei, kommen mir zwei Ursachen in den Sinn. Zum einen fallen die Prim­zahlen und ihre Summen nicht zufäl­lig. Zum anderen sind meine Ausgangs­annahmen über ihre Dichte nicht hinrei­chend genau.

Für den mittleren Abstand der Zahlen aus i Summan­den setzte ich iln(n/i) an, was von i gleich­großen Summan­den m=n/i ausgeht, in deren Nähe die Prim­zahlen den Abstand lnm aufweisen. Die unter­schied­liche Größe der Summan­den wirkt sich nur minimal und nach meinen Über­legungen auch in die andere Richtung aus.

Anders steht es um die wahre Dichte der Prim­zahlen [1]. Um 10.000 ist sie immer noch ein Prozent geringer als angesetzt. Doch im Bereich von 8001 bis 9000 sind zwei Prozent zu erklären. Dazu ist genauer hinzusehen: Bei n=8500 kommt man auf die maxi­male Summan­den­zahl k=2√(n/lnn)=61. Im Mittel sind es i=k/lnk=15, womit ein normaler Summand bei n/i=570 liegt, wo die Dichte der Prim­zahlen durchaus die ange­setzte um zwei Prozent unter­schreitet.

Liegt n im Milliarden­bereich, bleibt von diesem Effekt nichts übrig. Es muß also einen anderen Grund haben, weshalb bis 260 Milli­arden nur 5722 Neun­fach­treffer gezählt wurden, was einer Treffer­rate von 63,2 statt der vorher­gesagten 64,5 Prozent entspräche. Die verwen­dete Formel setzt Zufäl­ligkeit voraus, von der man nur bei geringen Treffer­zahlen ausgehen darf. Zur Verdeut­lichung habe ich einmal 7 Treffer in zehn Objekte durch­gerechnet:

Treffer	70 Prozent	7 aus 10	in 3 Salven	mit Abstand
0	49,6%	47,8%	44,8%	45,8%
1	34,8%	37,2%	41,6%	40,9%
2	12,2%	12,4%	12,4%	12,5%
3	2,84%	2,30%	1,20%	1,36%
4	0,50%	0,26%	keine	keine
5	0,07%	0,02%	keine	keine
6	81ppm	6,3ppm	keine	keine
7	8,1ppm	0,1ppm	keine	keine
8	0,7ppm	keine	keine	keine

Die zweite Spalte zeigt einfach die Wahr­schein­lich­keiten für i-fache Treffer, wenn in eine sehr große Zahl n von Objekten 0,7n mal völlig zufäl­lig geschos­sen wird. In der drit­ten Spalte sind es nur n=10 Objekte und 7 Schuß. Natur­gemäß sind Achtfach­treffer nicht mehr möglich und die Wahr­schein­lich­keiten für hohe Treffer­zahlen geringer. Auch die Über­lebens­chance (i=0) fällt etwas ab, wäh­rend im Gegen­zuge die Rate der Einzel­treffer steigt. Insge­samt ist der Effekt aber nicht berau­schend, obwohl n=10 doch so klein ist.

Feuert man nicht zufällig, sondern in einer einzigen Salve 7 Schuß ab, so fallen auch 7 tot um. Die Wahr­schein­lich­keit für 0 Treffer wäre 30 Prozent. Die Primzahl­summen bis zur Zahl n liegen in k=2√(n/lnn) Salven. Die vierte Spalte zeigt n=10 Objekte und k=3 Salven zu 3, 2 und 2 Schuß. Die Über­lebens­rate sinkt aber­mals, und mehr als dreimal kann keiner getrof­fen werden. Zum Aus­gleich steigt die Zahl der Einzel­treffer erneut an.

Die Primzahlsalven weisen eine weitere Abweichung vom Zufall auf. Zwischen zwei Tref­fern liegt immer ein Mindest­abstand, für den ich die Werte 2, 4 und 4 ange­setzt und die Wahr­schein­lich­keiten der fünften Spalte erhalten habe. Der Unter­schied ist minimal, doch über­raschend: Der Salven­effekt wird teil­weise aufge­hoben.

Kurz: Das Beispiel soll deutlich machen, daß die Rate der Neun­fach­treffer bis 260 Milli­arden möglicher­weise nicht einfach berech­net werden kann, als würde völlig will­kürlich 168 Milli­arden mal hinein­geschossen. Ihr Zurück­bleiben um den Faktor zwei ist durchaus plau­sibel. Um dies letzt­lich zu bestä­tigen, müßte ich bis in den Milli­arden­bereich rechnen oder die Ergeb­nisse anderer einsehen.

Doch habe ich es mir ein­facher gemacht und ein nur wenige Sekunden lau­fendes Pro­gramm geschrie­ben, das alle Treffer bis 1 Million ermittelt. Und schon ab 200.000 weichen diese Zahlen nur noch um weniger als ein Promille von den errech­neten Werten ab. Es ist geradezu beängsti­gend, wie gleich­mäßig und mit der Vorher­sage im Ein­klang die wirk­lichen Anzahlen verlaufen.

[1] Mathworld

Aus einem voran­gehenden Kommentar ist noch die Frage offen, warum im klein­zahligen Bereich die Anzahl der Einzel­treffer deutlich hinter der Erwar­tung zurück­bleibt. So werden 680 Treffer im Bereich von 501 bis 1500 gezählt, was 344 bis 345 einfach getrof­fene Zahlen erwar­ten ließe. In Wirk­lich­keit sind es aber mit 306 deutlich weniger.

Treffer	Zufall	Realität	u und g	p, v, g	modulo 6
0	50,66%	52,70%	50,89%	49,75%	52,06%
1	34,45%	30,60%	34,14%	35,77%	31,65%
2	11,71%	13,30%	11,68%	11,67%	13,11%
3	2,65%	2,90%	2,72%	2,40%	2,65%

Die Tabelle zeigt in der zweiten Spalte die zu erwar­tenden Treffer­zahlen, wenn 680 mal völlig zufällig in den Tausender­block geschos­sen würde. Die wahren Werte stehen in Spalte drei. Die Abwei­chung muß darin begrün­det sein, daß die Prim­zahlen und ihre Summen eben doch nicht zufäl­lig fallen, was sich im klein­zahligen Bereich deut­lich bemer­kbar macht.

Von der 2 abgesehen sind alle Prim­zahlen ungerade. Somit bilden gerade Sum­man­den­zahlen fast immer gerade und ungerade immer ungerade Summen. Naturgemäß werden die geraden Zahlen (g) nicht so häufig getroffen wie die ungeraden (u):

g(n) ≈ s(n) - ln2/lnn
u(n) ≈ s(n) + ln2/lnn

Für n=1000 ist der Zu- bzw. Abschlag 0,1 in sehr guter Übereinstimmung mit den 292 geraden und den 388 ungeraden Treffern im Bereich von 501 bis 1500. Fielen sie in diesen beiden Zahl­bereichen zufällig, so ergäben sich die Anteile der vierten Tabellen­spalte. Das ist kein berau­schender Effekt, der bei den Doppel­treffern nicht zufällig auch noch in die falsche Rich­tung weist.

Die nächste Idee könnte sein, auch noch die Prim­zahlen gesondert zu betrachten. Dazu ermittelt man die echten Treffer­dichten auf allen Zahlen (r) und auf den unge­raden Zahlen (v).

r(n) ≈ s(n) - 1/lnn
v(n) ≈ s(n) - (2-ln2)/lnn

Die daraus resul­tieren­den Quoten in Spalte fünf weisen in die falsche Richtung, was daran liegt, daß die Primzahl­salve explizit berück­sichtigt wurde. Salven aber vermin­dern die Nicht­treffer und die hohen Treffer.

Viel stärker ist ein anderer Zusammen­hang: Die Summen dreier Prim­zahlen treffen gerne wieder auf solche. Weil alle Prim­zahlen vom Typ 6k±1 sind, trifft dies auch für drei­viertel aller Summen aus drei Prim­zahlen zu. Die Drei­fach­sum­men treffen also dreimal häufiger eine Primzahl wie der reine Zufall. Sehr oft führt die Summe dreier Prim­zahlen so zu keinen Einzel­treffern, sondern macht aus einem einzelnen einen doppelten. Normaler­weise ergibt das zwei Einzel­treffer weniger. Zum Ausgleich sind es ein Doppel­treffer und eine nicht getrof­fene Zahl mehr.

Im Bereich von 501 bis 1500 gibt es 144 Primzahlen und 57 Dreifach­summen. Es wären also nur 8 Doppel­treffer aus beiden zu erwarten. Tatsächlich sind es mit 22 fast dreimal soviele. Gehe ich von 22-8=14 Dop­pel­treffern und Nicht­treffern mehr sowie 14+14=28 Ein­fach­treffern weniger aus als der reine Zufall der Spalte zwei vorgibt, so komme ich auf die Wahr­schein­lich­keiten sechsten Spalte.

Das erklärt den Löwen­anteil der Diffe­renz zwischen dem reinen Zufall und der Reali­tät. Es kommen ähnliche Effekte hinzu, denen ich gerne den Rest zuschiebe. Sie genauer zu quanti­fizieren, erspare ich mir, denn diese Zusammen­hänge sind nicht so wichtig wie eine Landung auf dem Mond, für dessen Bahn­berech­nung hunderte von Störungen zu berück­sich­tigen sind.