Zahlwort

Die Übertragung des naiven Siebes von Eratosthenes (im n-ten Schritt werden die echten Viel­fachen von n+1gestrichen) zum Sieb von Jose­phus (jede (n+1)-te der verblie­benen Zahlen wird ent­fernt) läßt deut­lich weniger Zahlen übrig. Um auf eine mit den Prim­zahlen vergleich­bare Dichte zu kommen, soll nunmehr analog zum nor­malen Sieb des Era­tosthe­nes nur nach der (n+1)-ten verblie­benen Zahl p(n) jede folgende p(n)-te gestri­chen werden. Für den Bereich bis 71 sieht das wie folgt aus:

                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-|---|
4   7  |||-|-O---|-|---|-----|-|---|-X-----|---|-|---|-----|-|---X-|-----|---|
5  11  |||-|-|---O-|---|-----|-|---|-------|---|-|---|-----|-X-----|-----|---|
       123 5 7  11 13  17   23 25  29     37  41 43  47    53     61    67  71

Im ersten Schritt (n=1) ist p(n)=p(1)=2 die zweite Zahl (O) unter allen natür­lichen. Ent­fernt (X) werden deshalb alle geraden Zahlen außer der 2 selbst. Für den zweiten Schritt ist p(2)=3 die dritte unter den verblie­benen (|) Zahlen. So werden 9, 15, 21, 27, ... entfernt. Das ist jede sechste Zahl. Die 4 fehlt, doch die 5 steht noch. Also p(4)=5, wodurch im dritten Schritt 19, 35, 49 und 65 ent­fallen. Für den vierten ist p(4)=7, wodurch 31 und 59 gestri­chen werden. Nun p(5)=11, daß 55 dran glauben muß. Weitere Schritte sind nicht erforder­lich, da nach p(6)=13 keine 13 Zah­len mehr im Sieb sind.

Setzt man den Prozeß bis ins Unendliche fort, so bleiben die ludic numbers 1, p(2), p(3), p(4), ... übrig. [1] Einen verbind­lichen deut­schen Namen haben sie meines Wissens nicht. [2] Und sie beginnen von den Prim­zahlen abwei­chend mit der Eins. [3]

Genaue Angaben über die Dichte der ludic numbers scheint es nicht zu geben. Sie ist wohl den Prim­zahlen ähnlich, bleibt aber etwas dahinter zurück. Jedenfalls bis 1 Mil­lion. Darunter gibt es 78.498 Prim­zahlen, aber nur 66.164 ludic numbers. Dazwi­schen liegt 10^6/ln(10^6)≈72.382. Trotzdem ent­sprechen die ersten acht den nicht­zusam­menge­setzten Zahlen. Erst darauf folgt 19 als die kleinste nonludic prime.

[1] The On-Line Encyclopedia of Integer Sequences. Ludic numbers A003309, ludic primes A192503, nonludic primes A192505.
[2] Leider findet selbst die wissenschaft­liche Begriffs­bildung nicht mehr in deut­scher Sprache statt, und es nützt auch nichts, ameri­kanische Serien gesehen zu haben oder den Google-​Über­setzer bedienen zu können, um für die ludic numbers einen verbind­lichen deut­schen Begriff zu finden.
[3] Ich hielte es für sinnvoll, wie beim modernen Sieb des Erato­sthenes die 1 außen vor zu lassen, mit der 2 zu beginnen und den n-ten Schritt mit der n-ten statt der (n+1)-ten Zahl auszu­führen, also 1 als nonludic zu sehen.

19 | Sieb des Eratosthenes | Sieb von Josephus