Hauptmenü öffnen

BeispieleBearbeiten

  •   ist eine Sierpiński-Zahl.
  • Die folgenden Zahlen sind bekannte Sierpiński-Zahlen  :
78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909, 965431, … (Folge A076336 in OEIS)
Ist   eine dieser Zahlen, so ist   für alle   zusammengesetzt. Man erhält niemals eine Primzahl.

GegenbeispielBearbeiten

Die Zahl   ist keine Sierpinski-Zahl, da in der Folge   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   nennt man Prothsche Primzahl.

Sierpinski-ProblemBearbeiten

Das Sierpiński-Problem lautet: Welche ist die kleinste Sierpinski-Zahl? 1962 hat John L. Selfridge gezeigt, dass 78557 eine Sierpinski-Zahl ist.[1] 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   kleiner als 78557 eine Zahl   gefunden werden, so dass die resultierende Proth-Zahl   eine Primzahl ist. Dieser Beweis ist (Stand 8. Juli 2019) bereits für alle   bis auf 5 Ausnahmen erfolgt, diese sind:

21181, 22699, 24737, 55459 und 67607 [1][2][3]

Die möglicherweise kleinste Sierpiński-Zahl   ist eine zusammengesetzte Zahl.

Das prime Sierpiński-Problem beschäftigt sich damit, ob   die kleinste prime Sierpiński-Zahl ist.[4] 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: 8. Juli 2019):

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

Das erweiterte Sierpiński-Problem beschäftigt sich damit, ob   tatsächlich die zweitkleinste Sierpiński-Zahl ist.[4][5] Um dies zu überprüfen, müssen neben den 11 oben genannten Zahlen noch zusätzlich die folgenden 13 zusammengesetzten Zahlen überprüft werden (wobei die ersten drei Zahlen schon im ursprünglichen Problem auftauchen) (Stand: 8. Juli 2019):

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

Riesel-ZahlBearbeiten

Eine Riesel-Zahl (benannt nach dem schwedischen Mathematiker Hans Riesel) ist eine natürliche, ungerade Zahl  , für die die unendliche Zahlenfolge   mit   keine Primzahlen enthält.

BeispieleBearbeiten

  •   ist eine Riesel-Zahl.
  • 1956 bewies Hans Riesel, dass es unendlich viele ganze Zahlen   gibt, so dass   nicht prim, also zusammengesetzt ist für alle positiven ganzen Zahlen  .[6]
  • Die folgenden Zahlen sind bekannte Riesel-Zahlen  :
509203, 762701, 777149, 790841, 992077, … (Folge A101036 in OEIS)
Ist   eine der oberen Zahlen, so ist   für alle   zusammengesetzt. Man erhält niemals eine Primzahl.

GegenbeispielBearbeiten

Die Zahl   ist keine Riesel-Zahl, da in der Folge   wenigstens eine Primzahl auftritt: 45, 91, 183, 367

Die kleinste Riesel-ZahlBearbeiten

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

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   wenigstens ein einziges   finden würde, sodass   eine Primzahl ist. Dann würde diese Zahl k als Kandidat für die kleinste Riesel-Zahl ausscheiden.

Brier-ZahlBearbeiten

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

  und  

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-ProblemBearbeiten

Bisher musste das   bei   immer eine positive ganze Zahl sein, also  . Was passiert aber, wenn man die Hochzahl negativ werden lässt? Sei also   mit  . Dann erhält man  . Nimmt man nur den Zähler dieser Bruchzahl, so erhält man die Zahl  .

Eine duale Sierpiński-Zahl ist eine ungerade natürliche Zahl  , für die   für alle natürlichen Zahlen   zusammengesetzt sind (man erhält also niemals eine Primzahl). Es gibt bzw. gab zwei Vermutungen, diese dualen Sierpiński-Zahlen betreffend:

  • Vermutung 1: Die Menge dieser dualen Sierpiński-Zahlen   ist ident zur Menge der Sierpiński-Zahlen. Dies zu beweisen ist das duale Sierpiński-Problem.
  • Vermutung 2: Die Zahl   ist die kleinste duale Sierpiński-Zahl. Diese zweite Vermutung konnte schon bewiesen werden. Das bedeutet, dass   für alle natürlichen Zahlen   zusammengesetzt ist. Gleichzeitig dürfte   aber auch die kleinste Sierpiński-Zahl sein (siehe Sierpiński-Problem).

Es gibt also kein  , welches kleiner als   ist, für welches   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   so lange ein geeignetes   sucht, bis man eines gefunden hat, für welches   eine Primzahl ergibt. Dieses Internet-Projekt mit dem Namen Five or Bust[8] hat somit seinen Zweck erfüllt und aus einer Vermutung eine Gewissheit gemacht (der Name kommt von fünf verschiedenen  , 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  , von denen man vor dem Projekt keine Primzahlen gekannt hat, lauteten:

k=2131, 28433, 40291, 41693 und 75353

Bei   erhält man erst bei   eine Primzahl, das heißt, dass   die kleinste Primzahl ist, die in der Folge   vorkommt. Weitere hohe Primzahlen erhält man für   und  , nämlich   bzw.   (somit sind   und   Primzahlen). Gleichzeitig erhält man aber für diese drei   sehr schnell Primzahlen der Form  , nämlich  ,   und  . Für das eigentliche Sierpiński-Problem machen diese drei   also keinerlei Schwierigkeiten. Umgekehrt kennt man zum Beispiel für   noch kein geeignetes  , sodass   eine Primzahl ergibt (es ist eines der fünf übrig gebliebenen Problemfälle beim Projekt Seventeen or Bust). Beim dualen Sierpiński-Problem macht dieses   aber kein Problem, denn schon für   erhält man die Primzahl  .

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

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 unbekannt, sehr groß 28 9
22.699 unbekannt, sehr groß 26 8
24.737 unbekannt, sehr groß 17 6
28.433 7830457 2357207 2249255 677094
40.291 8 8 9092392 2737083
41.693 33 15 5146295 1549190
55.459 unbekannt, sehr groß 14 5
67.607 unbekannt, sehr groß 46549 14013
75.353 1 6 1518191 457022

Die kleinsten  , für die   erstmals eine Primzahl ergibt (wobei   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  , die zu einem gegebenen   erstmals eine auf eine Primzahl führen, meistens sehr klein. In den meisten Fällen ist tatsächlich  . Es existieren lediglich einige wenige Fälle, bei denen man zu einem gegebenen   ein sehr hohes   benötigt, um erstmals eine Primzahl zu finden. Die folgende Liste gibt alle 28 existierenden   bis inklusive 78557 an, die ein dementsprechend hohes   benötigen, damit   eine Primzahl ergibt (oder, wie im Fall  , keine Primzahl existiert) und für welches auch   gilt. (eine umgekehrte Argumentation lautet: zu folgenden ungeraden   ist die Zahl   für alle   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-ProblemBearbeiten

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

Im Gegensatz zum ursprünglichen Sierpiński-Problem kann man diesmal gleich von vornherein viele gerade   ausschließen. Wenn man zum Beispiel wegen der Untersuchung der   vom Sierpiński-Problem weiß, dass   eine Primzahl ist, kann man daraus sofort folgern, dass   auch eine Primzahl ist und man kann somit   sofort aus der Liste der potentiellen geraden Sierpiński-Zahlen streichen. Ebenso ist   und   eine Primzahl und somit scheidet auch   und   sofort als gerader Sierpiński-Kandidat aus, ohne dass man eine besondere Rechnung angestellt haben muss.

Es gibt aber auch gerade  , 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  . In diesem Fall kann man aber leider keine 2 herausheben, sodass man über   eine Aussage treffen könnte. Somit muss man für dieses   mit roher Rechengewalt eine Primzahl finden. Hat man aber eine gefunden, in diesem Fall  , so kann man wieder weitere   ausschließen. In diesem Fall   und  .

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   irgendwann einmal eine Primzahl der Form   finden wird (mit einem sehr hohen  ), kann man sofort daraus schließen, dass   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   sofort folgern, dass auch   eine Primzahl ist (nämlich die gleiche). Weiters wäre die noch unentdeckte Primzahl der Form   eine Lösung, die aus der Liste der obigen 4 Zahlen nur noch einen einzigen Problemfall übrig lassen würden:  .

Es stellt sich die Frage, ob   jemals eine Primzahl werden kann. Es ist   und somit hätte diese gesuchte Primzahl die Form   mit  . Primzahlen der Form   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   sein und somit mindestens 2.585.827.973 Stellen haben (diese Fermat-Zahl   ist tatsächlich die kleinste Zahl der Form  , die eine Primzahl sein könnte, von der man es aber noch nicht weiss). Die größte bekannte Primzahl hat im Moment aber lediglich 24.862.048 Stellen (eine Mersenne-Primzahl, Stand: 15. April 2019), welches gerade einmal 0,96 % der Stellen sind, die   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   in absehbarer Zeit keine Primzahl finden wird. Möglicherweise gibt es auch tatsächlich keine Primzahl für dieses  . Dies würde aber bedeuten, dass   die erste gerade (und insgesamt auch kleinste) Sierpiński-Zahl wäre.

Duales Riesel-ProblemBearbeiten

Bisher musste das   bei   immer eine positive ganze Zahl sein, also  . Was passiert aber, wenn man wie schon bei den Sierpiński-Zahlen die Hochzahl negativ werden lässt? Sei also   mit  . Dann erhält man  . Nimmt man nur den Betrag des Zählers dieser Bruchzahl, so erhält man die Zahl  .

Eine duale Riesel-Zahl ist eine ungerade natürliche Zahl  , für die   für alle natürlichen Zahlen   zusammengesetzt sind (man erhält also niemals eine Primzahl). Es gibt zwei Vermutungen, diese dualen Riesel-Zahlen betreffend:

  • Vermutung 1: Die Menge dieser dualen Riesel-Zahlen   ist ident zur Menge der Riesel-Zahlen. Dies zu beweisen ist das duale Riesel-Problem.
  • Vermutung 2: Die Zahl   ist die kleinste duale Riesel-Zahl. Diese zweite Vermutung resultiert allerdings aus der obigen Vermutung 1. Das bedeutet, dass   für alle natürlichen Zahlen   zusammengesetzt ist. Gleichzeitig dürfte   aber auch die kleinste Riesel-Zahl sein (siehe Riesel-Problem).

Die Bedingung   verrät, dass man das Problem auf zweierlei Arten angehen kann. Man stößt bei der Suche nach Primzahlen der Form   auch auf negative Zahlen, wenn   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: 2n – k < 0 ist erlaubtBearbeiten

Dann stößt man bei der Suche nach Primzahlen der Form   auch auf negative Zahlen, deren Beträge Primzahlen sind. In diesem Fall ist dann  .

Unter diesen Voraussetzungen gibt es noch viele  , für welche man noch kein geeignetes   kennt, sodass   eine Primzahl ergibt. Die kleinste davon ist  .

Ungerade natürliche Zahlen   mit  , für welche   immer zusammengesetzte Zahlen ergeben (also niemals Primzahlen sind), nennt man de Polignac-Zahlen (eine dazu äquivalente Definition lautet: eine de Polignac-Zahl   ist eine ungerade Zahl, die nicht die Form   mit   hat [10]). 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: 2n – k < 0 ist nicht erlaubtBearbeiten

Dann darf man bei der Suche nach Primzahlen der Form   nicht auf negative Zahlen stoßen. In diesem Fall ist dann  .

Die kleinsten  , für die   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  , für welche man noch kein geeignetes   kennt, sodass   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-ProblemBearbeiten

Beim geraden Riesel-Problem muss   eine gerade natürliche Zahl sein. Es stellt sich die Frage, ob es ein gerades   gibt, welches eine Riesel-Zahl ist (für das also alle Zahlen der Form   immer zusammengesetzte Zahlen, also niemals Primzahlen, sind) [11].

Wie schon beim geraden Sierpiński-Problem kann man gleich von vornherein viele gerade   ausschließen. Zum Beispiel weiß man wegen der Untersuchung der   vom Riesel-Problem, dass   eine Primzahl ist und somit   als Riesel-Zahl nicht in Frage kommt. Aus dieser Tatsache kann man aber sofort folgern, dass auch   und   und   und so fort, Primzahlen sind, die somit für das gerade Riesel-Problem als potentielle gerade Riesel-Zahlen ausfallen. Wegen dieses einen erfolgreich ausgeschlossenen   kann man also sofort, ohne längere Rechnung, elf Werte für  , nämlich k=238, 476, 952, 1904, 3808, 7616, 15232, 30464, 60928, 121856 und 243712 ausschließen. Erst bei   kann man keine 2 mehr herausheben, da man sonst   erhalten würde, wobei aber 0 als Hochzahl weder beim Sierpiński- noch beim Riesel-Problem erlaubt ist. Der Wert   kann erst durch die Primzahl   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  , die zu sehr niedrigen Primzahlen geführt haben, wie zum Beispiel   kann man keine weiteren geraden   herausrechnen. Somit muss man auch für Vielfache von 69, also zuallererst für   eine geeignete Primzahl finden. Ist diese gefunden, in diesem Fall  , so kann man wieder höhere   ausschließen. In diesem Fall   und  . Dann ist man wieder bei   angelangt und muss für   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   als potentielle gerade Riesel-Kandidaten auszuschließen, die eine Hochzahl   zwischen   und   haben. Der untersten Tabelle kann man entnehmen, dass damit schon 254233   wegfallen, also keine geraden Riesel-Zahlen sein können. Erst ab Hochzahlen   benötigt man, je nach Rechenleistung, ein paar Tage bis Jahre.

Der unteren Tabelle kann man entnehmen, dass mit höheren Hochzahlen