Glückliche Zahlen
wuerg, 20.07.2023 21:17
Das Sieb des Eratosthenes streicht in seiner naiven Form mit den natürlichen Zahlen beginnend im n-ten Schritt die echten Vielfachen von n+1. Entfernt man dagegen jede (n+1)-te verbliebene Zahl so entsteht das Sieb von Josephus. Man kann sich im Sieb des Eratosthenes auf die Streichung der echten Vielfachen der (n+1)-ten im Sieb verbliebenen Zahl p(n) beschränken. Macht man das auch in Josephus-Manier und streicht jede p(n)-te Zahl aus dem Sieb, so entstehen die pseudo-lucky numbers. [1] Bis 71 sieht das wie folgt aus:
Streicht man p(n)=n+1 nicht, was zunächst die 2 im ersten und sodann die 3 im dritten Schritt betrifft, so entsteht eine ganz andere Folge
Gibt es pseudo-lucky numbers, so auch wirklich glückliche [2]. Sie entstehen in Josephus-Analogie aus dem Sieb des Eratosthenes, wenn man die Siebschritte etwas vermenschlicht und für p(n) statt der (n+1)-ten verbliebenen Zahl einfach die kleinste nach p(n-1) aus dem vorangehenden Schritt wählt. Dazu wird p(0)=1 gesetzt. Also für die lucky numbers: Man beginnt mit allen natürlichen Zahlen und p(0)=1. Im n-ten Siebschritt ist p(n) die minimale im Sieb verbliebene Zahl größer p(n-1), woraufhin jede p(n)-te daraus entfernt wird. Bis 71 sieht das wir folgt aus:
Wieder kann man sich der 2 erbarmen und p(n)=n nicht streichen, muß dieses Privileg allerdings auch der 3 zugestehen:
Die Prominenz der glücklichen Zahlen beruht vermutlich auf einem ihrer Urheber, Stanislaw Marcin Ulam. [3] Es bestand wohl die Hoffnung, durch sie etwas über Primzahlen herauszufinden, zumal sie ähnlich entstehen und eine nur leicht geringere Dichte aufweisen. So gibt es bis zur einer Million 78.498 Primzahlen und immerhin 71.919 glückliche Zahlen, gut in der Nähe von 10^6/ln(10^6)≈72.382.
Wie man das Sieb des Eratosthenes ohne die 1 starten kann, um nur die Primzahlen ohne die 1 zu erhalten, so beginnt man das Sieb der glücklichen Zahlen normalerweise mit den ungeraden, um das Problem mit der 2 zu umgehen und wieder einfach die (n+1)-te Zahl im Sieb als p(n) nehmen zu können. Da liegt es nahe, die gleiche Methode auch auf den geraden Zahlen zu probieren:
[1] The On-Line Encyclopedia of Integer Sequences. Pseudo-lucky numbers A249876. Lucky numbers heißen im deutschen Sprachraum glückliche Zahlen. Für pseudo-lucky numbers ist mir keine verbindliche Bezeichnung bekannt. Gut wäre scheinglücklich.
[2] The On-Line Encyclopedia of Integer Sequences. Glückliche Zahlen A00959, glückliche Primzahlen A031157 (darunter auch das Paar 37-73), ungerade zusammengesetzte unglückliche Zahlen A032584, glückliche Quadratzahlen A031162, glückliche Zwillinge A031160.
[3] Neben Ulam werden stets Gardiner, Lazarus und Metropolis genannt, weil die vier gemeinsam im Jahre 1956 die heute glücklich genannten Zahlen vorstellten. Wer die drei anderen sind, scheint vergessen. Ich dachte zunächst an eine Internet-Kopie-Kopie-Kopie eines Schreibfehlers, weil Gardner einiges über glückliche Zahlen schrieb. Doch der heißt Martin, der andere Verna Gardiner. Und Tony Gardiner war noch etwas zu jung.
[4] The On-Line Encyclopedia of Integer Sequences. Even-lucky numbers (ELN) A045954 und ihre Hälften A045989
[5] Natürlich gibt es auch die mir fremde Siebtheorie als mathematische Disziplin, wozu die hier vorgestellten Siebe wohl so gut wie nichts beitragen. Mir reichen die Erinnerungen an die analytische Zahlentheorie mit ihren nervigen Umsummierungen.
Sieb des Eratosthenes | Josephus-Problem | Sieb von Josephus | ludic numbers
1 2 3 4 5 6 7
n p(n) 12345678901234567890123456789012345678901234567890123456789012345678901
1 2 |X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|
2 5 | | O | X | | | | X | | | | X | | | | X | | | | X | | | | X | | | | X |
3 7 | | | O | | X | | | | | | X | | | | | | X | | | | | | X |
4 11 | | | | O | | | | | X | | | | | | | | | | X | | |
5 13 | | | | | O | | | | | | X | | | | | | | | | |
6 17 | | | | | | O | | | | | | | | | X | | | | |
7 21 | | | | | | | O | | | | | | | | | | | | X
1 3 5 7 11 13 17 21 23 25 31 35 41 43 45 47 55 57 63 65
Im ersten Schritt (n=1) ist p(n)=2 die zweite (n+1=2) Zahl unter allen natürlichen. Deshalb wird jede zweite Zahl gestrichen, auch p(n)=2 selbst. Es bleiben die ungeraden Zahlen. Im folgenden Schritt (n=2) ist p(n)=5 die dritte im Sieb verbliebene Zahl. So fällt mit 9, 19, 29, 39, ... jede fünfte durch das Sieb. Das sind die auf 9 endenden Zahlen. Für n=3 ist p(n)=7, womit 15, 33, 51 und 67 im Abstand von 18 durchfallen. Nun p(4)=11, wodurch 27 und 61 entfallen, p(5)=13 entfernt 37, p(6)=17 die 53 und p(7)=21 schließlich 71.Streicht man p(n)=n+1 nicht, was zunächst die 2 im ersten und sodann die 3 im dritten Schritt betrifft, so entsteht eine ganz andere Folge
1 2 3 4 5 6 7
n p(n) 12345678901234567890123456789012345678901234567890123456789012345678901
1 2 |O|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|
2 3 ||O | | X | | X | | X | | X | | X | | X | | X | | X | | X | | X | | X |
3 5 ||| O X | | | | X | | | | X | | | | X | | | | X |
4 11 ||| | O | | | | | X | | | | | | | | | |
5 13 ||| | | O | | | | | | X | | | | | | |
6 17 ||| | | | O | | | | | | | | | X | |
123 5 11 13 17 19 25 29 35 41 47 49 55 59 65 71
die der On-Line Encyclopedia of Integer Sequences unbekannt ist. Um die Flut der Siebe zu mehren, könnte ich sie dort einreichen.Gibt es pseudo-lucky numbers, so auch wirklich glückliche [2]. Sie entstehen in Josephus-Analogie aus dem Sieb des Eratosthenes, wenn man die Siebschritte etwas vermenschlicht und für p(n) statt der (n+1)-ten verbliebenen Zahl einfach die kleinste nach p(n-1) aus dem vorangehenden Schritt wählt. Dazu wird p(0)=1 gesetzt. Also für die lucky numbers: Man beginnt mit allen natürlichen Zahlen und p(0)=1. Im n-ten Siebschritt ist p(n) die minimale im Sieb verbliebene Zahl größer p(n-1), woraufhin jede p(n)-te daraus entfernt wird. Bis 71 sieht das wir folgt aus:
1 2 3 4 5 6 7
n p(n) 12345678901234567890123456789012345678901234567890123456789012345678901
1 2 |X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|
2 3 | O X | | X | | X | | X | | X | | X | | X | | X | | X | | X | | X | | X
3 7 | | O | | | X | | | | | | X | | | | | | X | | |
4 9 | | | O | | | | X | | | | | | | | X | | |
5 13 | | | | O | | | | | | | X | | | | | |
6 15 | | | | | O | | | | | | | | X | | |
1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69
Im ersten Schritt ist p(1)=2 die kleinste Zahl nach p(0)=1. Damit entfallen wiederum die geraden Zahlen. Die 2 ist weg, doch die 3 noch da, also p(2)=3, womit 5, 11, 17, 23, ... durchfallen. Nun ist 7 die kleinste Zahl nach der 3 im Sieb. Es werden 19, 39 und 61 gestrichen. Durch p(4)=9 verschwinden 27 und 57, p(5)=13 entfernt die 45 und p(6)=15 schließlich die 55. Die folgenden Schritte sind überflüssig, da schon p(7)=21 bei nur noch 17 Zahlen im Sieb.Wieder kann man sich der 2 erbarmen und p(n)=n nicht streichen, muß dieses Privileg allerdings auch der 3 zugestehen:
1 2 3 4 5 6 7
n p(n) 12345678901234567890123456789012345678901234567890123456789012345678901
1 2 |O|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|
2 3 ||O | | X | | X | | X | | X | | X | | X | | X | | X | | X | | X | | X |
3 5 ||| O X | | | | X | | | | X | | | | X | | | | X |
4 11 ||| | O | | | | | X | | | | | | | | | |
5 13 ||| | | O | | | | | | X | | | | | | |
6 17 ||| | | | O | | | | | | | | | X | |
123 5 11 13 17 19 25 29 35 41 47 49 55 59 65 71
Erneut entsteht eine ganz andere Folge, die nicht in der On-Line Encyclopedia of Integer Sequences zu finden ist.Die Prominenz der glücklichen Zahlen beruht vermutlich auf einem ihrer Urheber, Stanislaw Marcin Ulam. [3] Es bestand wohl die Hoffnung, durch sie etwas über Primzahlen herauszufinden, zumal sie ähnlich entstehen und eine nur leicht geringere Dichte aufweisen. So gibt es bis zur einer Million 78.498 Primzahlen und immerhin 71.919 glückliche Zahlen, gut in der Nähe von 10^6/ln(10^6)≈72.382.
Wie man das Sieb des Eratosthenes ohne die 1 starten kann, um nur die Primzahlen ohne die 1 zu erhalten, so beginnt man das Sieb der glücklichen Zahlen normalerweise mit den ungeraden, um das Problem mit der 2 zu umgehen und wieder einfach die (n+1)-te Zahl im Sieb als p(n) nehmen zu können. Da liegt es nahe, die gleiche Methode auch auf den geraden Zahlen zu probieren:
1 2 3 4 5 6 1 2 3 4 5 6
n p(n) 13579135791357913579135791357913 p(n) 2468024680246802468024680246802468
1 3 |OX||X||X||X||X||X||X||X||X||X|| 4 |O|X|||X|||X|||X|||X|||X|||X|||X||
2 7 ||-O|-||-X|-||-||-|X-||-||-||-X| 6 ||O-||X-|||-||X-|||-||X-|||-||X-||
3 9 ||-|O-||--|-|X-||-|--||-||-|X--| 10 |||-O|--|||-|X--|||-||--|||-|X--||
4 13 ||-||-O|--|-|--||-|--|X-||-|---| 12 |||-|O--|||-|---||X-||--|||-|---||
5 15 ||-||-|O--|-|--||-|--|--||-X---| 18 |||-||--O||-|---||--||--|||-|---X|
Links im Bild entstehen aus den ungeraden Zahlen wieder die lucky numbers, rechts aus den geraden die even-lucky numbers (ELN). [4] Ja, des Siebens ist kein Ende. [5][1] The On-Line Encyclopedia of Integer Sequences. Pseudo-lucky numbers A249876. Lucky numbers heißen im deutschen Sprachraum glückliche Zahlen. Für pseudo-lucky numbers ist mir keine verbindliche Bezeichnung bekannt. Gut wäre scheinglücklich.
[2] The On-Line Encyclopedia of Integer Sequences. Glückliche Zahlen A00959, glückliche Primzahlen A031157 (darunter auch das Paar 37-73), ungerade zusammengesetzte unglückliche Zahlen A032584, glückliche Quadratzahlen A031162, glückliche Zwillinge A031160.
[3] Neben Ulam werden stets Gardiner, Lazarus und Metropolis genannt, weil die vier gemeinsam im Jahre 1956 die heute glücklich genannten Zahlen vorstellten. Wer die drei anderen sind, scheint vergessen. Ich dachte zunächst an eine Internet-Kopie-Kopie-Kopie eines Schreibfehlers, weil Gardner einiges über glückliche Zahlen schrieb. Doch der heißt Martin, der andere Verna Gardiner. Und Tony Gardiner war noch etwas zu jung.
[4] The On-Line Encyclopedia of Integer Sequences. Even-lucky numbers (ELN) A045954 und ihre Hälften A045989
[5] Natürlich gibt es auch die mir fremde Siebtheorie als mathematische Disziplin, wozu die hier vorgestellten Siebe wohl so gut wie nichts beitragen. Mir reichen die Erinnerungen an die analytische Zahlentheorie mit ihren nervigen Umsummierungen.
Sieb des Eratosthenes | Josephus-Problem | Sieb von Josephus | ludic numbers
... comment
