Sierpiński-Zahl

Eine Sierpinski-Zahl (benannt nach dem polnischen Mathematiker Wacław Sierpiński) ist eine natürliche, ungerade Zahl $k$, für die die unendliche Zahlenfolge $k\cdot 2^{n}+1$ mit $n\geq 1$ keine Primzahlen enthält.

Beispiele

Die folgenden Zahlen sind bekannte Sierpiński-Zahlen $k$:

78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909, 965431, … (Folge A076336 in OEIS)

Ist $k$ eine der oberen Zahlen, so ist $k\cdot 2^{n}+1$ für alle $n$ zusammengesetzt. Man erhält niemals eine Primzahl.

Gegenbeispiel

Die Zahl $k=19$ ist keine Sierpinski-Zahl, da in der Folge $19\cdot 2^{n}+1$ wenigstens eine Primzahl auftritt: 39, 77, 153, 305, 609, 1217, 2433, ... Das sechste Glied der Folge, 1217, ist eine Primzahl. Das genügt zum Nachweis, dass 19 keine Sierpiński-Zahl ist. Ob noch weitere Primzahlen in dieser Folge auftreten oder nicht (das 10-te Glied ist die Primzahl 19457), ist unerheblich.

Primzahlen der Form $k\cdot 2^{n}+1$ nennt man Prothsche Primzahl.

Sierpinski-Problem

Das Sierpiński-Problem lautet: Welche ist die kleinste Sierpinski-Zahl? 1962 hat John L. Selfridge gezeigt, dass 78557 eine Sierpinski-Zahl ist. Es ist jedoch noch nicht bekannt, ob 78557 die kleinste Sierpinski-Zahl ist. Es wird aber vermutet, dass es sich um die kleinste Sierpinski-Zahl handelt. Das Internet-Projekt Seventeen or Bust beschäftigt sich mit diesem Problem.

Um den Beweis durchzuführen, muss für jedes $k$ kleiner als 78557 eine Zahl $n$ gefunden werden, so dass die resultierende Proth-Zahl $N=k\cdot 2^{n}+1$ eine Primzahl ist. Dieser Beweis ist (Stand 14. November 2016) bereits für alle $k$ bis auf 5 Ausnahmen erfolgt, diese sind:

21181, 22699, 24737, 55459 und 67607

Die möglicherweise kleinste Sierpiński-Zahl $k=78557=17\cdot 4621$ ist eine zusammengesetzte Zahl. Das prime Sierpiński-Problem beschäftigt sich damit, ob $k=271129$ die kleinste prime Sierpiński-Zahl ist. Um dies zu überprüfen, müssen die folgenden 10 Primzahlen überprüft werden (wobei die ersten zwei Zahlen schon in obigem Problem auftauchen) (Stand: 14. November 2016):

k = 22699, 67607, 79309, 79817, 152267, 156511, 168451, 222113, 225931, 237019

Das erweiterte Sierpiński-Problem beschäftigt sich damit, ob $k=271129$ tatsächlich die zweitkleinste Sierpiński-Zahl ist. Um dies zu überprüfen, müssen neben den 11 oben genannten Zahlen noch zusätzlich die folgenden 14 zusammengesetzten Zahlen überprüft werden (wobei die ersten drei Zahlen schon im ursprünglichen Problem auftauchen) (Stand: 10. Januar 2015):

k = 21181, 24737, 55459, 91549, 99739, 131179, 163187, 193997, 200749, 202705, 209611, 227723, 229673, 238411

Riesel-Zahl

Eine Riesel-Zahl (benannt nach dem schwedischen Mathematiker Hans Riesel) ist eine natürliche, ungerade Zahl $k$, für die die unendliche Zahlenfolge $k\cdot 2^{n}-1$ mit $n\geq 1$ keine Primzahlen enthält.

Beispiele

1956 bewies Hans Riesel, dass es unendlich viele ganze Zahlen $k$ gibt, so dass $k\cdot 2^{n}-1$ nicht prim, also zusammengesetzt ist für alle positiven ganzen Zahlen $n$.

Die folgenden Zahlen sind bekannte Riesel-Zahlen $k$:

509203, 762701, 777149, 790841, 992077, … (Folge A101036 in OEIS)

Ist $k$ eine der oberen Zahlen, so ist $k\cdot 2^{n}-1$ für alle $n$ zusammengesetzt. Man erhält niemals eine Primzahl.

Gegenbeispiel

Die Zahl $k=23$ ist keine Riesel-Zahl, da in der Folge $23\cdot 2^{n}-1$ wenigstens eine Primzahl auftritt: 45, 91, 183, 367

Die kleinste Riesel-Zahl

Riesel selbst fand 1956 mit 509.203 eine Riesel-Zahl. Es ist jedoch noch nicht bekannt, ob 509.203 die kleinste Riesel-Zahl ist. Um dies zu beweisen, muss man noch die folgenden 49 Zahlen kontrollieren, ob sie Riesel-Zahlen sind oder nicht:

2293, 9221, 23669, 31859, 38473, 46663, 67117, 74699, 81041, 93839, 97139, 107347, 121889, 129007, 143047, 146561, 161669, 192971, 206039, 206231, 215443, 226153, 234343, 245561, 250027, 315929, 319511, 324011, 325123, 327671, 336839, 342847, 344759, 362609, 363343, 364903, 365159, 368411, 371893, 384539, 386801, 397027, 409753, 444637, 470173, 474491, 477583, 485557 und 494743

Es würde ausreichen, wenn man zu jeder der obigen Zahlen $k$ wenigstens ein einziges $n$ finden würde, sodass $k\cdot 2^{n}-1$ eine Primzahl ist. Dann würde diese Zahl k als Kandidat für die kleinste Riesel-Zahl ausscheiden.

Brier-Zahl

Durch Eric Brier wurde nach positiven ganzen Zahlen k gesucht, die gleichzeitig Sierpinski- und Riesel-Zahl sind, d.h.

$k\cdot 2^{n}+1$ und $k\cdot 2^{n}-1$

sind für alle n stets zusammengesetzt. Derartige Zahlen heißen Brier-Zahlen.

Die erste 1998 gefundene Brier-Zahl ist die 41-stellige

k = 29364695660123543278115025405114452910889

Yves Gallot ermittelte 2000 eine 27-stellige Brier-Zahl

k = 878503122374924101526292469

2007 fanden Michael Filaseta, Carrie Finch und Mark Kozek die damals kleinste bekannte 24-stellige Brier-Zahl

k = 143665583045350793098657

Mittlerweile kennt man noch kleinere, aber immer noch mindestens 22-stellige Brier-Zahlen:

3316923598096294713661, 10439679896374780276373, 11615103277955704975673, 12607110588854501953787, … (Folge A076335 in OEIS)

Duales Sierpiński-Problem

Eine duale Sierpiński-Zahl ist eine ungerade natürliche Zahl $k$, für die $2^{n}+k$ für alle natürlichen Zahlen $n$ zusammengesetzt sind (man erhält also niemals eine Primzahl). Es gibt eine Vermutung, dass die Menge dieser dualen Sierpiński-Zahlen k ident ist zur Menge der Sierpiński-Zahlen. Dies zu beweisen ist das duale Sierpiński-Problem.

Die zweite Vermutung, nämlich dass k=78557 die kleinste duale Sierpiński-Zahl ist, konnte schon bewiesen werden. Das bedeutet, dass $2^{n}+78557$ für alle natürlichen Zahlen n zusammengesetzt ist. Gleichzeitig dürfte k=78557 aber auch die kleinste Sierpiński-Zahl sein (siehe Sierpinski-Problem).

Es gibt also kein k, welches kleiner als 78557 ist, für welches $2^{n}+k$ niemals eine Primzahl ergibt. Dieser Beweis gelang wie schon beim noch laufenden Internet-Projekt Seventeen or Bust durch die Brute-Force-Methode, indem man für jedes k so lange ein geeignetes n sucht, bis man eines gefunden hat, für welches $2^{n}+k$ eine Primzahl ergibt. Dieses Internet-Projekt mit dem Namen Five or Bust hat somit seinen Zweck erfüllt und aus einer Vermutung eine Gewissheit gemacht (der Name kommt von fünf k, die damals noch zu keiner bekannten Primzahl geführt haben). Jedenfalls brachte auch dieser Beweis einige sehr große Primzahlen zu Tage. Die fünf k, von denen man vor dem Projekt keine Primzahlen gekannt hat, lauteten:

k=2131, 28433, 40291, 41693 und 75353

Bei k=2131 erhält man erst bei n=4583176 eine Primzahl, das heißt, dass $2^{4583176}+2131$ die kleinste Primzahl ist, die in der Folge $2^{n}+2131$ vorkommt. Weitere hohe Primzahlen erhält man für k=40291 und k=41693, nämlich n=9092392 bzw. n= 5146295 (somit sind $2^{9092392}+40291$ und $2^{5146295}+41693$ Primzahlen). Gleichzeitig erhält man aber für diese drei k sehr schnell Primzahlen der Form $k\cdot 2^{n}+1$, nämlich $2131\cdot 2^{44}+1$, $40291\cdot 2^{8}+1$ und $41693\cdot 2^{33}+1$. Für das eigentliche Sierpiński-Problem machen diese drei k also keinerlei Schwierigkeiten. Umgekehrt kennt man zum Beispiel für k=21181 noch kein geeignetes n, sodass $21181\cdot 2^{n}+1$ eine Primzahl ergibt (es ist eines der fünf Problemfälle beim Projekt Seventeen or Bust). Beim dualen Sierpiński-Problem macht dieses k aber kein Problem, denn schon für n=28 erhält man die Primzahl $2^{28}+21181$.

In einer Tabelle zusammengefasst erkennt man die jeweils sechs größten Primzahlen beim Sierpiński-Problem und beim dualen Sierpiński-Problem bis zu k=78557:

Sierpiński-Problem			duales Sierpiński-Problem
k	n	Stellen von k·2n+1	n	Stellen von 2n+k
2.131	44	17	4583176	1379674
8.543	5793	1748	1191375	358640
10.223	31172165	9383761	19	6
21.181			28	9
22.699			26	8
24.737			17	6
28.433	7830457	2357207	2249255	677094
40.291	8	8	9092392	2737083
41.693	33	15	5146295	1549190
55.459			14	5
67.607			46549	14013
75.353	1	6	1518191	457022

Die kleinsten $n$, für die $2^{n}+k$ erstmals eine Primzahl ergibt (wobei $k$ ungerade ist) verrät die folgende Liste:

1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 3, 2, 1, 1, 4, 2, 1, 2, 1, 1, 2, 1, 5, 2, 1, 3, 2, 1, 1, 8, 2, 1, 2, 1, 1, 4, 2, 1, 2, 1, 7, 2, 1, 3, 4, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 7, 4, 5, 3, 4, 2, 1, 2, 1, 3, 2, 1, 1, 10, 3, 3, 2, 1, 1, ... (Folge A067760 in OEIS)

Wie man erkennen kann, sind die Hochzahlen n, die zu einem gegebenen k erstmals eine auf eine Primzahl führen, meistens sehr klein. In den meisten Fällen ist tatsächlich n<k. Es existieren lediglich einige wenige Fälle, bei denen man zu einem gegebenen k ein sehr hohes n benötigt, um erstmals eine Primzahl zu finden. Die folgende Liste gibt alle 28 existierenden k bis inklusive 78557 an, die ein dementsprechend hohes n benötigen, damit $2^{n}+k$ eine Primzahl ergibt (oder, wie im Fall k=78557, keine Primzahl existiert) und für welches auch n>k gilt. (eine umgekehrte Argumentation lautet: zu folgenden ungeraden k ist die Zahl $2^{n}+k$ für alle n<k immer zusammengesetzt):

773, 2131, 2491, 4471, 5101, 7013, 8543, 10711, 14717, 17659, 19081, 19249, 20273, 21661, 22193, 28433, 35461, 37967, 39079, 40291, 41693, 48527, 60443, 60451, 60947, 64133, 75353, 78557 (Folge A033919 in OEIS)

Gerades Sierpiński-Problem

Im Gegensatz zum ursprünglichen Sierpiński-Problem, bei dem $k$ eine natürliche, ungerade Zahl sein muss, ist beim geraden Sierpiński-Problem das $k$ eine natürliche gerade Zahl. Wieder stellt sich die Frage, ob es bis $k=78557$ kein gerades $k$ gibt, welches eine Sierpiński-Zahl ist .

Im Gegensatz zum ursprünglichen Sierpiński-Problem kann man diesmal gleich von vornherein viele gerade $k$ ausschließen. Wenn man zum Beispiel wegen der Untersuchung der $k$ vom Sierpiński-Problem weiß, dass $5107\cdot 2^{8}+1$ eine Primzahl ist, kann man daraus sofort folgern, dass $5107\cdot 2\cdot 2^{7}+1=10214\cdot 2^{7}+1$ auch eine Primzahl ist und man kann somit $k=10214$ sofort aus der Liste der potentiellen geraden Sierpiński-Zahlen streichen. Ebenso ist $5107\cdot 2^{2}\cdot 2^{6}+1=20428\cdot 2^{6}+1$ und $5107\cdot 2^{3}\cdot 2^{5}+1=40856\cdot 2^{5}+1$ eine Primzahl und somit scheidet auch $k=20428$ und $k=40856$ sofort als gerader Sierpiński-Kandidat aus, ohne dass man eine besondere Rechnung angestellt haben muss.

Es gibt aber auch gerade $k$, bei denen man mit der sonst üblichen Brute-Force-Methode arbeiten muss. Zum Beispiel stößt man bei der Lösung des ursprünglichen Sierpiński-Problems auf die Primzahl $5111\cdot 2^{1}+1$. In diesem Fall kann man aber leider keine 2 herausheben, sodass man über $k=10222$ eine Aussage treffen könnte. Somit muss man für dieses $k$ mit roher Rechengewalt eine Primzahl finden. Hat man aber eine gefunden, in diesem Fall $10222\cdot 2^{6}+1$, so kann man wieder weitere $k$ ausschließen. In diesem Fall $k=20444$ und $k=40888$.

Momentan gibt es für das gerade Sierpiński-Problem 4 Zahlen, für die man noch nicht ausschließen kann, dass sie Sierpiński-Zahlen sind:

42362, 45398, 49474, 65536

Drei dieser vier Zahlen sind eng verwandt mit den 5 Problemfällen vom ursprünglichen Sierpiński-Problem (21181, 22699, 24737, 55459 und 67607). Wenn man zum Beispiel für $k=21181$ irgendwann einmal eine Primzahl der Form $21181\cdot 2^{n}+1$ finden wird (mit einem sehr hohen $n$), kann man sofort daraus schließen, dass $21181\cdot 2\cdot 2^{n-1}+1=42362\cdot 2^{n-1}+1$ ebenfalls eine Primzahl ist und schon hätte das gerade Sierpiński-Problem nur noch 3 Problemfälle. Analog kann man aus einer noch zu findenden Primzahl der Form $22699\cdot 2^{n}+1$ sofort folgern, dass auch $45398\cdot 2^{n-1}+1$ eine Primzahl ist (nämlich die gleiche). Weiters wäre die noch unentdeckte Primzahl der Form $24737\cdot 2^{n}+1=49474\cdot 2^{n-1}+1$ eine Lösung, die aus der Liste der obigen 4 Zahlen nur noch einen einzigen Problemfall übrig lassen würden: $k=65536$.

Es stellt sich die Frage, ob $65536\cdot 2^{n}+1$ jemals eine Primzahl werden kann. Es ist $65536=2^{16}$ und somit hätte diese gesuchte Primzahl die Form $2^{16}\cdot 2^{n}+1=2^{n+16}+1=:2^{m}+1$ mit $m:=n+16$. Primzahlen der Form $2^{m}+1$ sind aber Fermatsche Primzahlen und von diesen sind momentan nur fünf bekannt, nämlich 3, 5, 17, 257 und 65537. Pierre de Fermat vermutete zwar, dass es unendlich viele solche Fermatschen Primzahlen gibt, mittlerweile wird aber vermutet, dass es nur diese fünf Primzahlen von dieser Form gibt. Wenn es wirklich noch weitere Fermatsche Primzahlen gibt, so muss diese Zahl mindestens $F_{33}=2^{2^{33}}+1=2^{8589934592}+1$ sein und somit mindestens 2.585.827.973 Stellen haben (diese Fermat-Zahl $F_{33}$ ist tatsächlich die kleinste Zahl der Form $2^{n}+1$, die eine Primzahl sein könnte, von der man es aber noch nicht weiss). Die größte bekannte Primzahl hat im Moment aber lediglich 22.338.618 Stellen (eine Mersenne-Primzahl, Stand: 7. Januar 2016), welches gerade einmal 0,86 % der Stellen sind, die $F_{33}$ besitzt. Man ist also noch meilenweit von der Primzahlbestimmung von so riesigen Zahlen entfernt. Für das gerade Sierpiński-Problem bedeutet das aber, dass man für die Zahl $k=65536$ in absehbarer Zeit keine Primzahl finden wird. Möglicherweise gibt es auch tatsächlich keine Primzahl für dieses $k$. Dies würde aber bedeuten, dass $k=65536$ die erste gerade (und insgesamt auch kleinste) Sierpiński-Zahl wäre.

Duales Riesel-Problem

Eine duale Riesel-Zahl ist eine ungerade natürliche Zahl $k$, für die $|2^{n}-k|$ für alle natürlichen Zahlen $n$ zusammengesetzt sind (man erhält also niemals eine Primzahl). Es gibt eine Vermutung, dass die Menge dieser dualen Riesel-Zahlen ident ist zur Menge der Riesel-Zahlen. Dies zu beweisen ist das duale Riesel-Problem.

Es gibt eine zweite Vermutung, die allerdings aus der obigen Vermutung resultiert, nämlich dass $k=509203$ die kleinste duale Riesel-Zahl ist. Das bedeutet, dass $|2^{n}-509203|$ für alle natürlichen Zahlen $n$ zusammengesetzt ist. Gleichzeitig dürfte $k=509203$ aber auch die kleinste Riesel-Zahl sein (siehe Riesel-Problem).

Die Bedingung $|2^{n}-k|$ verrät, dass man das Problem auf zweierlei Arten angehen kann. Man stößt bei der Suche nach Primzahlen der Form $2^{n}-k$ auch auf negative Zahlen, wenn $2^{n}<k$ ist. Dieser Sachverhalt kann erlaubt sein, muss aber nicht erlaubt sein. Deswegen spaltet sich das duale Riesel-Problem in zwei Fälle auf.

Fall 1: 2ⁿ-k<0 ist erlaubt

Dann stößt man bei der Suche nach Primzahlen der Form $2^{n}-k$ auch auf negative Zahlen, deren Beträge Primzahlen sind. In diesem Fall ist dann $2^{n}<k$.

Unter diesen Voraussetzungen gibt es noch viele $k$, für welche man noch kein geeignetes $n$ kennt, sodass $|2^{n}-k|$ eine Primzahl ergibt. Die kleinste davon ist $k=2293$.

Ungerade natürliche Zahlen $k$ mit $k>2^{n}$, für welche $k-2^{n}>0$ immer zusammengesetzte Zahlen ergeben (also niemals Primzahlen sind), nennt man de Polignac-Zahlen (eine dazu äquivalente Definition lautet: eine de Polignac-Zahl $k$ ist eine ungerade Zahl, die nicht die Form $k=2^{n}+p$ mit $p\in \mathbb {P}$ hat ). Die ersten paar solcher Zahlen verrät die folgende Liste:

1, 127, 149, 251, 331, 337, 373, 509, 599, 701, 757, 809, 877, 905, 907, 959, 977, 997, 1019, 1087, 1199, 1207, 1211, 1243, 1259, 1271, 1477, ... (Folge A006285 in OEIS)

Fall 2: 2ⁿ-k<0 ist nicht erlaubt

Dann darf man bei der Suche nach Primzahlen der Form $2^{n}-k$ nicht auf negative Zahlen stoßen. In diesem Fall ist dann $2^{n}>k$.

Die kleinsten $n$, für die $2^{n}-k=p>0$ erstmals eine Primzahl ergibt, verrät die folgende Liste (aufsteigend für ungerade k=1, 3, 5, 7, 9,…):

2, 3, 3, 39, 4, 4, 4, 5, 6, 5, 5, 6, 5, 5, 5, 7, 6, 6, 11, 7, 6, 29, 6, 6, 7, 6, 6, 7, 6, 6, 6, 8, 8, 7, 7, 10, 9, 7, 8, 9, 7, 8, 7, 7, 8, 7, 8, 10, 7, 7, 26, 9, 7, 8, 7, 7, 10, 7, 7, 8, 7, 7, 7, 47, 8, 14, 9, 11, 10, 9, 10, 8, 9, 8, 8, ... (Folge A096502 in OEIS)

Die ersten $k$, für welche man noch kein geeignetes $n$ kennt, sodass $2^{n}-k$ eine Primzahl ergibt, lauten:

1871, 2293, 25229, 31511, 36971, 47107, 48959, 50171, 56351, 63431, 69427, 75989, 81253, 83381, 84491, 107857, 109649, 118567, 128263, 132217, 134557, 134579, 138847, 144337, 148091, 149797, 150179, 150641, 158369, 170531, 175709, 183313, 191759, ... (Folge A216189 in OEIS)

Gerades Riesel-Problem

Beim geraden Riesel-Problem muss $k$ eine gerade natürliche Zahl sein. Es stellt sich die Frage, ob es ein gerades $k<509203$ gibt, welches eine Riesel-Zahl ist (für das also alle Zahlen der Form $k\cdot 2^{n}-1$ immer zusammengesetzte Zahlen, also niemals Primzahlen, sind) .

Wie schon beim geraden Sierpiński-Problem kann man gleich von vornherein viele gerade $k$ ausschließen. Zum Beispiel weiß man wegen der Untersuchung der $k$ vom Riesel-Problem, dass $119\cdot 2^{12}-1=487423$ eine Primzahl ist und somit $k=119$ als Riesel-Zahl nicht in Frage kommt. Aus dieser Tatsache kann man aber sofort folgern, dass auch $119\cdot 2\cdot 2^{11}-1=238\cdot 2^{11}-1=487423$ und $119\cdot 2^{2}\cdot 2^{10}-1=476\cdot 2^{10}-1=487423$ und $119\cdot 2^{3}\cdot 2^{9}-1=952\cdot 2^{9}-1=487423$ und so fort, Primzahlen sind, die somit für das gerade Riesel-Problem als potentielle gerade Riesel-Zahlen ausfallen. Wegen dieses einen erfolgreich ausgeschlossenen $k=119$ kann man also sofort, ohne längere Rechnung, elf Werte für $k$, nämlich k=238, 476, 952, 1904, 3808, 7616, 15232, 30464, 60928, 121856 und 243712 ausschließen. Erst bei $119\cdot 2^{11}\cdot 2^{1}-1=243712\cdot 2^{1}-1=487423$ kann man keine 2 mehr herausheben, da man sonst $119\cdot 2^{12}\cdot 2^{0}-1=487424\cdot 2^{0}-1=487423$ erhalten würde, wobei aber 0 als Hochzahl weder beim Sierpiński- noch beim Riesel-Problem erlaubt ist. Der Wert $k=487424$ kann erst durch die Primzahl $487424\cdot 2^{4}-1=7798783$ als gerade Riesel-Zahl ausgeschlossen werden. Diesmal wieder durch die Brute-Force-Methode, also durch Ausnützung der rohen Rechengewalt eines Computers, der alle möglichen Werte so lange durchprobiert, bis er eine Primzahl gefunden hat. Auch aus ungeraden $k$, die zu sehr niedrigen Primzahlen geführt haben, wie zum Beispiel $69\cdot 2^{1}-1=137$ kann man keine weiteren geraden $k$ herausrechnen. Somit muss man auch für Vielfache von 69, also zuallererst für $k=2\cdot 69=138$ eine geeignete Primzahl finden. Ist diese gefunden, in diesem Fall $138\cdot 2^{3}-1=1103$, so kann man wieder höhere $k$ ausschließen. In diesem Fall $k=276$ und $k=552$. Dann ist man wieder bei $552\cdot 2^{1}-1=1103$ angelangt und muss für $k=1104$ wieder eine neue Berechnung mit der Brute-Force-Methode beginnen.

In der Praxis sind aber die Computer heutzutage so schnell, dass man sich obige Überlegungen ersparen kann. Binnen weniger Stunden ist es möglich, mit einem geeigneten Mathematik-Programm alle $k$ als potentielle gerade Riesel-Kandidaten auszuschließen, die eine Hochzahl $n$ zwischen $2^{0}=1$ und $2^{13}=16384$ haben. Der untersten Tabelle kann man entnehmen, dass damit schon 254233 $k$ wegfallen, also keine geraden Riesel-Zahlen sein können. Erst ab Hochzahlen $n>2^{13}$ benötigt man, je nach Rechenleistung, ein paar Tage bis Jahre.

Der unteren Tabelle kann man entnehmen, dass mit höheren Hochzahlen $2^{13}<n<2^{21}$ schon die meisten $k$ ausgeschlossen werden konnten. Insgesamt bleiben 53 verschiedene $k$ übrig, für die noch kein $n$ gefunden werden konnte, sodass $k\cdot 2^{n}-1$ eine Primzahl ist. 51 dieser 53 Zahlen sind die folgenden (Stand: 16. Februar 2016):

4586, 9172, 18344, 18442, 36688, 36884, 47338, 63718, 73376, 73768, 76946, 93326, 94676, 127436, 134234, 146752, 147536, 149398, 153892, 162082, 186652, 187678, 189352, 194278, 214694, 243778, 254872, 258014, 268468, 286094, 293122, 293504, 295072, 298796, 307784, 323338, 324164, 373304, 375356, 378704, 385942, 388556, 412078, 412462, 429388, 430886, 452306, 468686, 487556, 491122, 500054

Für diese $k$ wird man erst dann geeignete $n$ finden, wenn man für das ursprüngliche Riesel-Problem für gewisse im Moment noch problematische $k$ geeignete $n$ gefunden hat. Zum Beispiel kennt man für $k=2293$ noch kein $n$, sodass $k\cdot 2^{n}-1$ eine Primzahl ergibt. Deswegen ist $k=2293$ auch in der Liste der noch zu erledigenden $k$ im Abschnitt Riesel-Zahl enthalten. Hat man aber irgendwann einmal ein geeignetes $n$ gefunden, für welches $2293\cdot 2^{n}-1$ prim ist, dann wird dieses $n$ sehr groß sein. Dann ist aber auch $2293\cdot 2\cdot 2^{n-1}-1=4586\cdot 2^{n-1}-1$ eine Primzahl (nämlich dieselbe) und man kann aus der obigen Liste sofort, ohne eine besondere Rechnung angestellt zu haben, $k=4586$ eliminieren. Ebenso kann man mit derselben Argumentation auch sofort die Werte k=9172, 18344, 36688, 73376, 146752 und 293504 eliminieren. Insgesamt wären sofort 7 Werte aus obiger Liste zu entfernen, wenn man irgendwann für $k=2293$ eine geeignete Primzahl findet. Ebenso kann man für alle oben genannten 51 Werte Primzahlen finden. Man muss nur beim ursprünglichen Riesel-Problem die problematischen $k$ eliminieren, also geeignete Primzahlen der Form $k\cdot 2^{n}-1$ finden.

Übrig bleiben nur noch 2 Werte für $k$, die man separat untersuchen muss. Diese lauten (Stand: 1. April 2008):

351134, 478214

Für diese $k$ sind noch keine Primzahlen der Form $k\cdot 2^{n}-1$ bekannt. Wenn man zum Beispiel $k=351134$ betrachtet, kann man feststellen, dass man eine Primzahl der Form $351134\cdot 2^{n}-1=175567\cdot 2\cdot 2^{n}-1=175567\cdot 2^{n+1}-1$ benötigt. Beim ursprünglichen Riesel-Problem macht $k=175567$ auch tatsächlich kein Problem, zumal $175567\cdot 2^{1}-1=351133$ eine Primzahl ergibt. Nur leider kann man bei dieser Primzahl nicht $2^{1}$ herausheben, denn dann würde man $175567\cdot 2^{1}\cdot 2^{0}-1=351134\cdot 2^{0}-1$ erhalten. Für das Riesel-Problem ist eine Hochzahl 0 aber nicht erlaubt. Somit muss man eine größere Primzahl für $k=175567$ suchen, damit man auch für $k=351134$ eine geeignete findet. Und so eine größere Primzahl ist eben im Moment noch nicht bekannt, obwohl man schon bis $n=5200000$ gesucht hat. Analog verhält es sich mit dem anderen Wert $k=478214$. In diesem Fall ist $k=239107\cdot 2^{1}-1=478214\cdot 2^{0}-1=478213$ die momentan einzige bekannte Primzahl, wobei aber $2^{0}$ nicht erlaubt ist. In diesem Fall hat man ebenfalls schon bis $n=5200000$ ergebnislos gesucht.

Das gerade Riesel-Problem ist also noch längst nicht gelöst. Es könnte durchaus sein, dass man ein gerades $k$ finden wird, für welches $k\cdot 2^{n}-1$ niemals eine Primzahl ist. Dann hätte man eine gerade Riesel-Zahl gefunden, die kleiner als 509203 ist. Es wird aber davon ausgegangen, dass es keine solche Zahl gibt.

Wie schnell findet man eine Primzahl für ein gegebenes k

Für die meisten $k$ findet man sehr schnell geeignete $n$, sodass $k\cdot 2^{n}\pm 1$ bzw. $2^{n}\pm k$ eine Primzahl ergibt. Um zu erkennen, wie schnell man eine Zahl $n$ zu einem gegebenen $k$ findet, sodass man erstmals eine Primzahl der jeweiligen Form erhält, definiert man $f_{m}$ als die Anzahl der $k$, für welche der Exponent $n$ im Intervall $2^{m}\leq n<2^{m+1}$ liegt. Die folgende Tabelle zeigt, wie schnell man die $k$ ausschließen kann. In der Tabelle werden folgende Variablen verwendet:

$n$ … kleinste Hochzahl, bei der man erstmals eine Primzahl der gegebenen Form erhält

$x$ … maximale Anzahl der Stellen von $2^{n}$

$f_{m}$ … Anzahl der $k$, für welche man im Intervall $2^{m}\leq n<2^{m+1}$ erstmals eine Primzahl findet

			$k\cdot 2^{n}+1$				$2^{n}+k$	$k\cdot 2^{n}-1$		$2^{n}-k$
			Sierpiński- Problem	primes Sierpiński- Problem	erweitertes Sierpiński- Problem	gerades Sierpiński- Problem	duales Sierpiński- Problem	Riesel- Problem	gerades Riesel- Problem	duales Riesel- Problem 2n<k	duales Riesel- Problem 2n>k
m	n	x	fm	fm’	fm’’	fm	fm	fm	fm	fm	fm
0	1	1	7238	1667	13491	7205	7707	39867	39980	42226	0
1	2 ≤ n ≤ 3	1	10194	2804	19709	10166	11622	59460	59474	66788	3
2	4 ≤ n ≤ 7	3	9582	3635	19803	9703	11091	62311	62112	71954	42
3	8 ≤ n ≤ 15	5	6272	3242	13909	6204	6161	45177	44869	48639	6220
4	16 ≤ n ≤ 31	10	3045	2140	7193	3052	1764	24478	24477	17286	199858
5	32 ≤ n ≤ 63	19	1445	1145	3197	1437	463	11668	11997	4031	33537
6	64 ≤ n ≤ 127	39	685	605	1451	629	202	5360	5459	1558	8166
7	128 ≤ n ≤ 255	77	331	322	656	351	92	2728	2671	785	3205
8	256 ≤ n ≤ 511	154	195	159	364	227	57	1337	1277	447	1449
9	512 ≤ n ≤ 1023	308	114	106	162	122	26	785	830	247	735
10	1024 ≤ n ≤ 2047	617	47	59	99	55	28	467	488	181	465
11	2048 ≤ n ≤ 4095	1233	34	45	67	38	18	289	275	131	278
12	4096 ≤ n ≤ 8191	2466	26	23	42	30	11	191	184	72	169
13	8192 ≤ n ≤ 16383	4932	11	17	30	7	4	125	140	45	108
14	16384 ≤ n ≤ 32767	9864	18	12	23	10	8	87	91	43	83
15	32768 ≤ n ≤ 65535	19729	12	5	14	18	6	62	59
16	65536 ≤ n ≤ 131071	39457	5	12	9	4	5	38	36
17	131072 ≤ n ≤ 262143	78913	5	5	3	1	3	35	45
18	262144 ≤ n ≤ 524287	157827	2	5	8	1	2	25	27
19	524288 ≤ n ≤ 1048575	315653	3	6	6	0	2	22	29
20	1048576 ≤ n ≤ 2097151	631306	2	3	3	0	2	18	9
21	2097152 ≤ n ≤ 4194303	1262612	1	1	5	4	1	13	14
22	4194304 ≤ n ≤ 8388607	2525223	3	2	1	5	2	8	5
23	8388608 ≤ n ≤ 16777215	5050445	2	1		3	1
	16777216 ≤ n		6	8		6	0
Summe:			39278	16029	80256	39278	39278	254601	254601	254601	254601

Sierpiński-Zahlen zur Basis b

Eine Sierpiński-Zahl zur Basis b ist eine natürliche Zahl $k$, sodass $k\cdot b^{n}+1$ für alle $n>0$ eine zusammengesetzte Zahl ergibt. Es darf also niemals eine Primzahl herauskommen.

Für $b=2$ erhält man die klassischen Sierpiński-Zahlen, die weiter oben vorgestellt wurden.

Allerdings ist die Situation nicht mehr ganz so einfach wie bei den klassischen Sierpiński-Zahlen. Denn wenn man zum Beispiel $b=3$ wählt, kann man recht schnell erkennen, dass jedes ungerade $k$ eine Sierpiński-Zahl zur Basis 3 wäre, weil jede Zahl der Form $k\cdot 3^{n}+1$ gerade und somit immer durch 2 teilbar ist und folglich niemals eine Primzahl ergibt (jede Potenz von 3 ist wieder ungerade, multipliziert mit einer ungeraden Zahl bleibt sie ungerade, und wegen +1 wird sie gerade). Um diese trivialen Fälle für potentiell interessante Sierpiński-Zahlen zur Basis b auszuschließen, muss man somit noch gewisse Vorkehrungen treffen, damit nur wirklich interessante, nichttriviale $k$ als Sierpiński-Zahlen zur Basis b in Frage kommen.

Bedingung

Die zusätzliche Bedingung für nichttriviale Sierpiński-Zahlen $k$ zur Basis b, sodass nicht eine einzelne Primzahl $p$ alle Zahlen der Form $k\cdot b^{n}+1$ teilt, ist die folgende:

$ggT(k+1,b-1)=1$

Es muss also der größte gemeinsamer Teiler von $k+1$ und $b-1$ gleich $1$ sein.

Beweis der Bedingung

Der Beweis funktioniert direkt.

Zuerst wird gezeigt, dass wenn eine Primzahl $p$ jedes $k\cdot b^{n}+1$ für alle $n\geq 0$ teilt, gelten muss:

$p$ teilt $ggT(k+1,b-1)$ und somit ist $ggT(k+1,b-1)\not =1$.

Angenommen, eine Primzahl $p\in \mathbb {P}$ teilt $k\cdot b^{n}+1$ für alle $n\geq 0$. Dann teilt $p$ auch $k\cdot b^{0}+1=k\cdot 1+1=k+1$ und $k\cdot b^{1}+1=k\cdot b+1$. Wenn $p$ aber sowohl $k+1$ als auch $k\cdot b+1$ teilt, dann teilt $p$ auch die Differenz dieser beider Terme, nämlich $(k\cdot b+1)-(k+1)=k\cdot b+1-k-1=k\cdot b-k=k\cdot (b-1)$. Somit muss $p$ auch $k$ oder $b-1$ teilen. Da $p$ schon $k+1$ teilt, kann $p$ nicht gleichzeitig $k$ teilen, also ist $p$ ein Teiler von $b-1$. Weil somit also $p$ ein Teiler von $k+1$ und $b-1$ sein muss, teilt $p$ auch den $ggT(k+1,b-1)$. Also ist $ggT(k+1,b-1)\not =1$.

Umgekehrt wird nun gezeigt, dass wenn $p$ ein Teiler von $ggT(k+1,b-1)$ ist, daraus gefolgert werden kann, dass $p$ auch ein Teiler von $k\cdot b^{n}+1$ für alle $n\geq 0$ sein muss.

Sei also $p$ ein Teiler von $ggT(k+1,b-1)$. Dann kann man mit den Rechenregeln der Kongruenz zeigen, dass gilt: $k\equiv -1\mod p$ und $b\equiv 1\mod p$ und somit gilt:

$k\cdot b^{n}+1\equiv -1\cdot 1^{n}+1\equiv 0\mod p$

Somit ist $p$ ein Teiler von $k\cdot b^{n}+1$.

Insgesamt wurde also gezeigt, dass $p$ die Zahlen $k\cdot b^{n}+1$ für alle $n\geq 0$ genau dann teilt, wenn $p$ ein Teiler von $ggT(k+1,b-1)$ ist. Der Beweis ist vollendet.

Tabelle der Sierpiński-Zahlen zur Basis b

Um den trivialen Fall auszuschließen, bei dem lediglich eine einzige (Prim-)Zahl $p$ alle Zahlen der Form $k\cdot b^{n}+1$ mit $n>0$ teilt und somit $k$ schon eine gesuchte Sierpiński-Zahl zur Basis b ist, muss zusätzlich die Bedingung $ggT(k+1,b-1)$ gefordert werden.

Nun kann man natürlich die Basis $b$ beliebig hoch werden lassen. Untersucht werden momentan aber „nur“ Basen bis $b\leq 1030$. Es folgt eine Tabelle mit dem momentanen Wissensstand (Stand: 15. Februar 2018) für Basen bis $b=30$:

b	vermutete kleinste Sierpiński-Zahl k	Problemfälle k, für die man noch keine Primzahlen kennt, die kleiner als die vermutete kleinste Sierpiński-Zahl k und keine Vielfachen von ebenfalls unbekannten Problemfällen sind; in Klammern sind ausgewählte Problemfälle, die Vielfache von anderen Problemfällen sind	größte so gefundene Primzahl
2	78557	21181, 22699, 24737, 55459, 65536, 67607 (insgesamt 6 Problemfälle)
3	125050976086	6363484, 8911036, 12663902, 14138648, 14922034, 18302632, 21497746, 23896396, 24019448, 24677704, 33224138, 33381178, 35821276, 37063498, 39431872, 46891088, 47628292, 54503602,… (diese 18 und noch 730599 weitere bis k ≤ 32.000.000.000 und ab k ≥ 40.000.000.000, also in diesen beiden Intervallen insgesamt 730617 Problemfälle)
4	66741	18534, 21181, 22699, 49474, 55459, 64494, 65536 (insgesamt 7 Problemfälle)
5	159986	6436, 7528, 10918, 26798, 29914, 31712, 36412, 41738, 44348, 44738, 45748, 51208, 58642, 60394, 62698, 64258, 67612, 67748, 71492, 74632, 76724, 81556, 83936, 84284, 90056, 92906, 93484, 105464, 118568, 126134, 138514, 139196, 152588 (insgesamt 33 Problemfälle)
6	174308	1296, 13215, 14505, 50252, 76441, 87800, 97131, 112783, 124125, 127688, 166753, 168610 (insgesamt 12 Problemfälle)
7	1112646039348	987144, 1613796, 1911142, 2052426, 2471044, 3778846, 4023946, 4300896, 4369704, 4455408, 4723986, 4783794, 4810884, 6551056, 7115518, 7248984, 8186656, 8566504, 9230674, 9284172, 9566736,… (diese 21 und noch 710 weitere bis k ≤ 50000000, also bis dahin insgesamt 731 Problemfälle)
8	1	keine Problemfälle mehr	keine
9	2344	2036
10	9175	100, 7666
11	1490	keine Problemfälle mehr
12	521	12
13	132	keine Problemfälle mehr
14	4	keine Problemfälle mehr
15	91218919470156	215432, 424074, 685812, 1936420, 2831648, 3100818, 3789018, 5074424, 5095268, 5311880, 5349258, 5382720, 5391260, 5437658, 5624046, 5624350, 5923260, 6022606, 6038592, 6079288, 6113172, 6201428, 6341914, 6438174, 6492284, 6729940, 6741008, 7370892, 7567724, 7759144, 7858272, 7976572, 8029172, 8340272, 8347462, 8371008, 8410850, 8446312, 8495324, 8592272, 8718584, 9051940, 9174358, 9189710, 9307436, 9352744, 9562550, 9564418, 9720238, 10033124,… (diese 50 und noch 821 weitere bis k<100000000, also bis dahin 871 Problemfälle)
16	2500	keine Problemfälle mehr
17	278	244
18	398	18
19	765174	1446, 2526, 2716, 3714, 4506, 4614, 6796, 10776, 14556, 15394, 15396, 15616, 16246, 17596, 19014, 19906, 20326, 20364, 21696, 24754, 25474, 29746, 29896, 29956, 30196, 36534, 38356, 39126, 39276, 42934, 43986, 44106, 45216, 45846, 46174, 50124, 53014, 55516, 57544, 59214,… (diese 40 und noch 520 weitere, also insgesamt 560 Problemfälle)
20	8	keine Problemfälle mehr
21	1002	keine Problemfälle mehr
22	6694	22, 5128
23	182	keine Problemfälle mehr
24	30651	656, 1099, 1851, 1864, 2164, 2351, 2586, 3404, 3526, 3609, 3706, 3846, 4606, 4894, 5129, 5316, 5324, 5386, 5889, 5974, 7276, 7746, 7844, 8054, 8091, 8161, 8369, 9279, 9304, 9701, 9721, 10026, 10156, 10531, 11346, 12799, 12969, 12991, 13716, 13984, 15921, 17334, 17819, 17876, 18006, 18204, 18911, 19031, 19094, 20219, 20731, 21459, 21526, 22289, 22356, 22479, 23844, 23874, 23981, 24784, 25964, 26279, 27344, 28099, 29009, 29091, 29349, 29464, 29566, 29601 (insgesamt 70 Problemfälle)
25	262638	222, 6436, 7528, 10918, 12864, 13548, 15588, 18576, 29914, 35970, 36412, 45330, 45748, 51208, 57240, 58434, 58642, 60394, 62698, 64258, 65610, 66678, 67612, 74632, 75666, 76896, 81186, 81556, 82962, 86334, 90240, 91038, 93378, 93484, 94212, 101958, 107472, 108720, 110304, 114516, 114726, 124164, 133990, 134172, 138514, 157548, 158560, 162756, 165270, 165504, 166620, 169324, 176916, 177022, 178972, 183028, 184414, 184456, 195016, 195144, 196236, 198840, 199174, 201382, 205906, 206982, 207544, 208690, 211860, 216282, 217140, 221304, 221740, 223690, 226992, 228982, 230998, 231328, 231390, 231906, 243108, 244438, 245010, 252468, 258942 (insgesamt 85 Problemfälle)
26	221	65, 155
27	8	keine Problemfälle mehr
28	4554	871, 4552
29	4	keine Problemfälle mehr
30	867	278, 588

Wie man erkennen kann, sind für gewisse Basen $b$ alle Problemfälle gelöst. Das bedeutet, dass die oben genannte Sierpiński-Zahl $k$ tatsächlich die kleinste Sierpiński-Zahl zu dieser Basis b ist und dass folglich alle Zahlen der Form $k\cdot b^{n}+1$ für alle $n>0$ zusammengesetzte Zahlen sind. Im Folgenden werden die kleinsten Teiler für die schon bewiesenen und die noch vermuteten kleinsten Sierpiński-Zahlen angegeben:

b	bewiesene kleinste Sierpiński-Zahl k	vermutete kleinste Sierpiński-Zahl k	(kleinste) Teiler von $k\cdot b^{n}+1$
2		78557	$78557\cdot 2^{n}+1$ hat immer mindestens einen der Teiler 3, 5, 7, 13, 19, 37 oder 73
3		125.050.976.086	$125050976086\cdot 3^{n}+1$ hat immer mindestens einen der Teiler 5, 7, 13, 17, 19, 37, 41, 193 oder 757
4		66741	$66741\cdot 4^{n}+1$ hat immer mindestens einen der Teiler 5, 7, 13, 17 oder 241
5		159986	$159986\cdot 5^{n}+1$ hat immer mindestens einen der Teiler 3, 7, 13, 31 oder 601
6		174308	$174308\cdot 6^{n}+1$ hat immer mindestens einen der Teiler 7, 13, 31, 37 oder 97
7		1.112.646.039.348	$1112646039348\cdot 7^{n}+1$ hat immer mindestens einen der Teiler 5, 13, 19, 43, 73, 181, 193 oder 1201
8	1		$1\cdot 8^{n}+1=(1\cdot 2^{n}+1)\cdot (1\cdot 4^{n}-1\cdot 2^{n}+1)$
9		2344	$2344\cdot 9^{n}+1$ hat immer mindestens einen der Teiler 5, 7, 13 oder 73
10		9175	$9175\cdot 10^{n}+1$ hat immer mindestens einen der Teiler 7, 11, 13 oder 37
11	1490		$1490\cdot 11^{n}+1$ hat immer mindestens einen der Teiler 3, 7, 19 oder 37
12		521	$521\cdot 12^{n}+1$ hat immer mindestens einen der Teiler 5, 13 oder 29
13	132		$132\cdot 13^{n}+1$ hat immer mindestens einen der Teiler 5, 7 oder 17
14	4		$4\cdot 14^{n}+1$ hat immer mindestens einen der Teiler 3 oder 5
15		91.218.919.470.156	$91218919470156\cdot 15^{n}+1$ hat immer mindestens einen der Teiler 13, 17, 113, 211, 241, 1489 oder 3877
16	2500		$2500\cdot 16^{n}+1=(50\cdot 4^{n}-10\cdot 2^{n}+1)\cdot (50\cdot 4^{n}+10\cdot 2^{n}+1)$
17		278	$278\cdot 17^{n}+1$ hat immer mindestens einen der Teiler 3, 5 oder 29
18		398	$398\cdot 18^{n}+1$ hat immer mindestens einen der Teiler 5, 13 oder 19
19		765174	$765174\cdot 19^{n}+1$ hat immer mindestens einen der Teiler 5, 7, 13, 127 oder 769
20	8		$8\cdot 20^{n}+1$ hat immer mindestens einen der Teiler 3 oder 7
21	1002		$1002\cdot 21^{n}+1$ hat immer mindestens einen der Teiler 11, 13 oder 17
22		6694	$6694\cdot 22^{n}+1$ hat immer mindestens einen der Teiler 5, 23 oder 97
23	182		$182\cdot 23^{n}+1$ hat immer mindestens einen der Teiler 3, 5 oder 53
24		30651	$30651\cdot 24^{n}+1$ hat immer mindestens einen der Teiler 5, 7, 13, 73 oder 79
25		262638	$262638\cdot 25^{n}+1$ hat immer mindestens einen der Teiler 7, 13, 31 oder 601
26		221	$221\cdot 26^{n}+1$ hat immer mindestens einen der Teiler 3, 7, 19 oder 37
27	8		$8\cdot 27^{n}+1=(2\cdot 3^{n}+1)\cdot (4\cdot 9^{n}-2\cdot 3^{n}+1)$
28		4554	$4554\cdot 28^{n}+1$ hat immer mindestens einen der Teiler 5, 29 oder 157
29	4		$4\cdot 29^{n}+1$ hat immer mindestens einen der Teiler 3 oder 5
30		867	$867\cdot 30^{n}+1$ hat immer mindestens einen der Teiler 7, 13, 19 oder 31

Es folgt noch eine Liste der vermuteten kleinsten Sierpiński-Zahlen zur Basis $2\leq b\leq 50$:

78557, 125050976086, 66741, 159986, 174308, 1112646039348, 1, 2344, 9175, 1490, 521, 132, 4, 91218919470156, 2500, 278, 398, 765174, 8, 1002, 6694, 182, 30651, 262638, 221, 8, 4554, 4, 867, 6360528, 1, 1854, 6, 214018, 1886, 2604, 14, 166134, 826477, 8, 13372, 2256, 4, 53474, 14992, 8, 1219, 2944, 16,… (Folge A123159 in OEIS)

Riesel-Zahlen zur Basis b

Eine Riesel-Zahl zur Basis b ist eine natürliche Zahl $k$, sodass $k\cdot b^{n}-1$ für alle $n>0$ eine zusammengesetzte Zahl ergibt. Es darf also niemals eine Primzahl herauskommen.

Für $b=2$ erhält man die klassischen Riesel-Zahlen, die weiter oben vorgestellt wurden.

Wie schon bei den Sierpiński-Zahlen zur Basis b ist auch die Situation bei Riesel-Zahlen zur Basis b nicht mehr ganz so einfach wie bei den klassischen Riesel-Zahlen. Denn wenn man wie vorher zum Beispiel $b=3$ wählt, kann man erkennen, dass jedes ungerade $k$ eine Riesel-Zahl zur Basis 3 wäre, weil jede Zahl der Form $k\cdot 3^{n}-1$ gerade und somit immer durch 2 teilbar ist und folglich niemals eine Primzahl ergibt (jede Potenz von 3 ist wieder ungerade, multipliziert mit einer ungeraden Zahl bleibt sie ungerade, und wegen −1 wird sie gerade). Um diese trivialen Fälle für potentiell interessantere Riesel-Zahlen zur Basis b auszuschließen, muss man somit wieder eine Vorkehrung treffen, damit nur wirklich interessante, nichttriviale $k$ als Riesel-Zahlen zur Basis b in Frage kommen.

Bedingung

Die zusätzliche Bedingung für nichttriviale Riesel-Zahlen $k$ zur Basis b, sodass nicht eine einzelne Primzahl $p$ alle Zahlen der Form $k\cdot b^{n}-1$ teilt, ist die folgende:

$ggT(k-1,b-1)=1$

Es muss also der größte gemeinsamer Teiler von $k-1$ und $b-1$ gleich $1$ sein.

Der Beweis dieser Bedingung funktioniert analog zum Beweis der Bedingung für Sierpiński-Zahlen zur Basis b.

Tabelle der Riesel-Zahlen zur Basis b

Um den trivialen Fall auszuschließen, bei dem lediglich eine einzige (Prim-)Zahl $p$ alle Zahlen der Form $k\cdot b^{n}-1$ mit $n>0$ teilt und somit $k$ schon eine gesuchte Riesel-Zahl zur Basis b ist, muss zusätzlich die Bedingung $ggT(k-1,b-1)$ gefordert werden.

Nun kann man wieder die Basis $b$ beliebig hoch werden lassen. Untersucht werden momentan aber wie schon bei Sierpiński-Zahlen „nur“ Basen bis $b\leq 1030$. Es folgt eine Tabelle mit dem momentanen Wissensstand (Stand: 12. Februar 2018) für Basen bis $b=30$:

b	vermutete kleinste Riesel-Zahl k	Problemfälle k, für die man noch keine Primzahlen kennt, die kleiner als die vermutete kleinste Riesel-Zahl k und keine Vielfachen von ebenfalls unbekannten Problemfällen sind	größte so gefundene Primzahl
2	509203	2293, 9221, 23669, 31859, 38473, 46663, 67117, 74699, 81041, 93839, 97139, 107347, 121889, 129007, 143047, 146561, 161669, 192971, 206039, 206231, 215443, 226153, 234343, 245561, 250027, 315929, 319511, 324011, 325123, 327671, 336839, 342847, 344759, 351134, 362609, 363343, 364903, 365159, 368411, 371893, 384539, 386801, 397027, 409753, 444637, 470173, 474491, 477583, 478214, 485557, 494743 (insgesamt 51 Problemfälle)
3	63064644938	3677878, 6878756, 10463066, 10691528, 10789522, 16874152, 18137648, 21368582, 29140796, 31064666, 38394682, 40175404, 40396658, 51672206, 52072432, 56244334, 57805042, 59077924,… (diese 18 und noch 272008 weitere, also insgesamt 272026 Problemfälle)
4	9	keine Problemfälle mehr
5	346802	3622, 4906, 23906, 26222, 35248, 35816, 52922, 63838, 64598, 66916, 68132, 71146, 76354, 81134, 88444, 92936, 102818, 102952, 109238, 109838, 109862, 127174, 131848, 134266, 136804, 143632, 145462, 145484, 146264, 146756, 147844, 151042, 152428, 154844, 159388, 164852, 170386, 170908, 177742, 182398, 187916, 189766, 190334, 194368, 195872, 201778, 204394, 206894, 207494, 213988, 231674, 238694, 239062, 239342, 246238, 248546, 259072, 265702, 267298, 271162, 273662, 285598, 285728, 298442, 304004, 313126, 318278, 322498, 325922, 327926, 335414, 338866 (insgesamt 72 Problemfälle)
6	84687	1597
7	408034255082	315768, 1356018, 1620198, 2096676, 2494112, 2539898, 2631672, 3423408, 3531018, 3587876, 3885264, 4322834, 4326672, 4363418, 4382984, 4635222, 4780002, 4870566, 4990788, 5119538,… (diese 20 und noch 8371 weitere bis k < 500000000, also bis dahin insgesamt 8391 Problemfälle)
8	14	keine Problemfälle mehr
9	4	keine Problemfälle mehr
10	10176	4421
11	862	keine Problemfälle mehr
12	25	keine Problemfälle mehr
13	302	keine Problemfälle mehr
14	4	keine Problemfälle mehr
15	36370321851498	381714, 4242104, 4502952, 5237186, 5854146, 7256276, 8524154, 9105446, 9756404,… (diese 9 und noch viele weitere ab k > 10000000)
16	9	keine Problemfälle mehr
17	86	keine Problemfälle mehr
18	246	keine Problemfälle mehr
19	144	keine Problemfälle mehr
20	8	keine Problemfälle mehr
21	560	keine Problemfälle mehr
22	4461	3656
23	476	404
24	4	keine Problemfälle mehr
25	36	keine Problemfälle mehr
26	149	keine Problemfälle mehr
27	8	keine Problemfälle mehr
28	144	keine Problemfälle mehr
29	4	keine Problemfälle mehr
30	1369	659, 1024

Auch in dieser Tabelle kann man erkennen, dass für gewisse Basen $b$ alle Problemfälle gelöst sind. Das bedeutet, dass die oben genannte Riesel-Zahl $k$ tatsächlich die kleinste Riesel-Zahl zu dieser Basis b ist und dass folglich alle Zahlen der Form $k\cdot b^{n}-1$ für alle $n>0$ zusammengesetzte Zahlen sind. Im Folgenden werden die kleinsten Teiler für die schon bewiesenen und die noch vermuteten kleinsten Riesel-Zahlen angegeben:

b	bewiesene kleinste Riesel-Zahl k	vermutete kleinste Riesel-Zahl k	(kleinste) Teiler von $k\cdot b^{n}-1$
2		509203	$509203\cdot 2^{n}-1$ hat immer mindestens einen der Teiler 3, 5, 7, 13, 17 oder 241
3		63.064.644.938	$63064644938\cdot 3^{n}-1$ hat immer mindestens einen der Teiler 5, 7, 13, 17, 19, 37, 41, 193 oder 757
4	9		$9\cdot 4^{n}-1=(3\cdot 2^{n}-1)\cdot (3\cdot 2^{n}+1)$
5		346802	$346802\cdot 5^{n}-1$ hat immer mindestens einen der Teiler 3, 7, 13, 31 oder 601
6		84687	$84687\cdot 6^{n}-1$ hat immer mindestens einen der Teiler 7, 13, 31, 37 oder 97
7		408.034.255.082	$408034255082\cdot 7^{n}-1$ hat immer mindestens einen der Teiler 5, 13, 19, 43, 73, 181, 193 oder 1201
8	14		$14\cdot 8^{n}-1$ hat immer mindestens einen der Teiler 3, 5 oder 13
9	4		$4\cdot 9^{n}-1=(2\cdot 3^{n}-1)\cdot (2\cdot 3^{n}+1)$
10		10176	$10176\cdot 10^{n}-1$ hat immer mindestens einen der Teiler 7, 11, 13 oder 37
11	862		$862\cdot 11^{n}-1$ hat immer mindestens einen der Teiler 3, 7, 19 oder 37
12	25		$25\cdot 12^{n}-1$ hat für ungerade n immer den Teiler 13 $25\cdot 12^{n}-1=(5\cdot 12^{\frac {n}{2}}-1)\cdot (5\cdot 12^{\frac {n}{2}}+1)$ für gerade n
13	302		$302\cdot 13^{n}-1$ hat immer mindestens einen der Teiler 5, 7 oder 17
14	4		$4\cdot 14^{n}-1$ hat immer mindestens einen der Teiler 3 oder 5
15		36.370.321.851.498	$36370321851498\cdot 15^{n}-1$ hat immer mindestens einen der Teiler 13, 17, 113, 211, 241, 1489 oder 3877
16	9		$9\cdot 16^{n}-1=(3\cdot 4^{n}-1)\cdot (3\cdot 4^{n}+1)$
17	86		$86\cdot 17^{n}-1$ hat immer mindestens einen der Teiler 3, 5 oder 29
18	246		$246\cdot 18^{n}-1$ hat immer mindestens einen der Teiler 5, 13 oder 19
19	144		$144\cdot 19^{n}-1$ hat für ungerade n immer den Teiler 5 $144\cdot 19^{n}-1=(12\cdot 19^{\frac {n}{2}}-1)\cdot (12\cdot 19^{\frac {n}{2}}+1)$ für gerade n
20	8		$8\cdot 20^{n}-1$ hat immer mindestens einen der Teiler 3 oder 7
21	560		$560\cdot 21^{n}-1$ hat immer mindestens einen der Teiler 11, 13 oder 17
22		4461	$4461\cdot 22^{n}-1$ hat immer mindestens einen der Teiler 5, 23 oder 97
23		476	$476\cdot 23^{n}-1$ hat immer mindestens einen der Teiler 3, 5 oder 53
24	4		$4\cdot 24^{n}-1$ hat für ungerade n immer den Teiler 5 $4\cdot 24^{n}-1=(2\cdot 24^{\frac {n}{2}}-1)\cdot (2\cdot 24^{\frac {n}{2}}+1)$ für gerade n
25	36		$36\cdot 25^{n}-1=(6\cdot 5^{n}-1)\cdot (6\cdot 5^{n}+1)$
26	149		$149\cdot 26^{n}-1$ hat immer mindestens einen der Teiler 3, 7, 31 oder 37
27	8		$8\cdot 27^{n}-1=(2\cdot 3^{n}-1)\cdot (4\cdot 9^{n}+2\cdot 3^{n}+1)$
28	144		$144\cdot 28^{n}-1$ hat für ungerade n immer den Teiler 29 $144\cdot 28^{n}-1=(12\cdot 28^{\frac {n}{2}}-1)\cdot (12\cdot 28^{\frac {n}{2}}+1)$ für gerade n
29	4		$4\cdot 29^{n}-1$ hat immer mindestens einen der Teiler 3 oder 5
30		1369	$1369\cdot 30^{n}-1$ hat für ungerade n immer mindestens einen der Teiler 7, 13 oder 19 $1369\cdot 30^{n}-1=(37\cdot 30^{\frac {n}{2}}-1)\cdot (37\cdot 30^{\frac {n}{2}}+1)$ für gerade n

Es folgt noch eine Liste der vermuteten kleinsten Riesel-Zahlen zur Basis $2\leq b\leq 50$:

509203, 63064644938, 9, 346802, 84687, 408034255082, 14, 4, 10176, 862, 25, 302, 4, 36370321851498, 9, 86, 246, 144, 8, 560, 4461, 476, 4, 36, 149, 8, 144, 4, 1369, 134718, 10, 16, 6, 287860, 4, 7772, 13, 4, 81, 8, 15137, 672, 4, 22564, 8177, 14, 3226, 36, 16,… (Folge A273987 in OEIS)

Weblinks

• Seventeen Or Bust (Distributed Computing-Projekt, englisch)
• PrimeGrid (Distributed Computing-Projekt, englisch)
• The Prime Glossary
• Status des Sierpinski-Problems
• Status des Riesel-Problems
• Yves Gallot, A search for some small Brier numbers, 2000
• Joe McLean, Brier Numbers
• M. Filaseta et al., On Powers Associated with Sierpinski Numbers, Riesel Numbers and Polignac’s Conjecture (PDF; 255 kB)
• Startseite des Internet-Projektes “Seventeen or Bust”
• Tabelle aller Vermutungen bis zur Basis 1030