Sieb von Josephus
Das Sieb des Erato­sthenes siebt in einer naiven Form aus den natür­lichen Zahlen im n‑ten Schritt die echten Viel­fachen von n+1 heraus. Das Sieb von Jose­phus [1] erhält man mit einer leich­ten Abwand­lung: Es wird einfach jede (n+1)‑te Zahl aus den ver­blie­benen gestri­chen. Das basiert auf dem Jose­phus-Problem: Wer von m im Kreis stehen­den Män­nern bleibt übrig, wenn jeder k‑te erschla­gen wird? Hier aber fehlt der Kreis, weshalb bis in die Unend­lich­keit zunächst jeder zweite, danach erneut von vorne begin­nend jeder dritte usw. erschla­gen wird. Bis 79 sieht das wie folgt aus:
           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 verblie­benen. Das sind 5, 11, 17, 23, ... im Abstand von 6. Danach jede vierte, wodurch 9, 21, 33, 45, ... getrof­fen werden. Im vierten Schritt müssen 15, 37, 55 und 75 dran glauben. So geht es weiter bis zum letzten erforder­lichen Schritt 9, in dem die 67 fällt.

Für die so bis in die Unend­lichkeit verblei­benden Zahlen gibt es meines Wissens keinen ver­breite­ten Namen. Wohl aber für andere eben­falls auf der Jose­phus-Vor­stellung beru­henden wie den lucky und den ludic numbers, die ein mit den Prim­zahlen ver­gleich­bares Wachstum auf­weisen, während die namen­losen Zahlen aus dem hier vorge­stellten Sieb von Jose­phus deut­lich dünner gesät sind. [2]

[1] Besser „nach“ Josephus, der selbst allen­falls Sand gesiebt hat. Von Flavius Jose­phus selbst gibt es nur eine merk­würdige Schil­derung, nach der jeder dritte von 41 Män­nern Selbst­mord verübte bis er selbst als vor­letzter an der Reihe war und sich gemein­sam 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

... link (0 Kommentare)   ... comment