Sieb von Josephus
wuerg, 27.02.2022 23:10
Das Sieb des Eratosthenes siebt in einer naiven Form aus den natürlichen Zahlen im n‑ten Schritt die echten Vielfachen von n+1 heraus. Das Sieb von Josephus [1] erhält man mit einer leichten Abwandlung: Es wird einfach jede (n+1)‑te Zahl aus den verbliebenen gestrichen. Das basiert auf dem Josephus-Problem: Wer von m im Kreis stehenden Männern bleibt übrig, wenn jeder k‑te erschlagen wird? Hier aber fehlt der Kreis, weshalb bis in die Unendlichkeit zunächst jeder zweite, danach erneut von vorne beginnend jeder dritte usw. erschlagen wird. Bis 79 sieht das wie folgt aus:
Für die so bis in die Unendlichkeit verbleibenden Zahlen gibt es meines Wissens keinen verbreiteten Namen. Wohl aber für andere ebenfalls auf der Josephus-Vorstellung beruhenden wie den lucky und den ludic numbers, die ein mit den Primzahlen vergleichbares Wachstum aufweisen, während die namenlosen Zahlen aus dem hier vorgestellten Sieb von Josephus deutlich dünner gesät sind. [2]
[1] Besser „nach“ Josephus, der selbst allenfalls Sand gesiebt hat. Von Flavius Josephus selbst gibt es nur eine merkwürdige Schilderung, nach der jeder dritte von 41 Männern Selbstmord verübte bis er selbst als vorletzter an der Reihe war und sich gemeinsam mit dem letzten den Römern ergab.
[2] The On-Line Encyclopedia of Integer Sequences. Sieb nach Josephus A000960, lucky numbers A000959, ludic numbers A003309.
Sieb des Eratosthenes | Josephus-Problem
1 2 3 4 5 6 7
n1234567890123456789012345678901234567890123456789012345678901234567890123456789
1|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|X|X|X|X|
2| | X | | X | | X | | X | | X | | X | | X | | X | | X | | X | | X | | X | | X |
3| | | X | | | X | | | X | | | X | | | X | | | X | | |
4| | | | X | | | | X | | | | X | | | | X |
5| | | | | X | | | | | X | | | | |
6| | | | | | X | | | | | | X |
7| | | | | | | X | | | | |
8| | | | | | | | X | | |
9| | | | | | | | | X |
1 3 7 13 19 27 39 49 63 79
Zunächst werden die geraden Zahlen gestrichen, dann jede dritte der verbliebenen. Das sind 5, 11, 17, 23, ... im Abstand von 6. Danach jede vierte, wodurch 9, 21, 33, 45, ... getroffen werden. Im vierten Schritt müssen 15, 37, 55 und 75 dran glauben. So geht es weiter bis zum letzten erforderlichen Schritt 9, in dem die 67 fällt.Für die so bis in die Unendlichkeit verbleibenden Zahlen gibt es meines Wissens keinen verbreiteten Namen. Wohl aber für andere ebenfalls auf der Josephus-Vorstellung beruhenden wie den lucky und den ludic numbers, die ein mit den Primzahlen vergleichbares Wachstum aufweisen, während die namenlosen Zahlen aus dem hier vorgestellten Sieb von Josephus deutlich dünner gesät sind. [2]
[1] Besser „nach“ Josephus, der selbst allenfalls Sand gesiebt hat. Von Flavius Josephus selbst gibt es nur eine merkwürdige Schilderung, nach der jeder dritte von 41 Männern Selbstmord verübte bis er selbst als vorletzter an der Reihe war und sich gemeinsam mit dem letzten den Römern ergab.
[2] The On-Line Encyclopedia of Integer Sequences. Sieb nach Josephus A000960, lucky numbers A000959, ludic numbers A003309.
Sieb des Eratosthenes | Josephus-Problem
... comment
