Einzelnen Beitrag anzeigen
  #16  
Alt 21.11.21, 17:00
Bernhard Bernhard ist offline
Moderator
 
Registriert seit: 14.06.2017
Beitr?ge: 2.635
Standard AW: Primzahlzwillinge

Das im ersten Beitrag verlinkte Thema im MatheBoard ist inklusive Autor zwar gesperrt, kann aber immerhin noch als Motivation für einen Primzahlgenerator für endliche Primzahlmengen herhalten.

Man findet so nach einer kleinen Korrektur sogar eine interessante Alternative, bzw. Erweiterung des Generators im WP-Artikel.

So gilt zB

p_1 * p_2 * ... * p_n + oder - p_(n+1)^m ist prim, solange die so berechnte Zahl kleiner als (p_(n+2))² ist. Der Beweis dazu ist trivial.

m muss dabei als positive ganze Zahl so gewählt werden, dass die erzeugte Zahl immer größer als 1 und kleiner als (p_(n+2))² ist.

EDIT: Im eigentlichen Thema würde man nun weiterkommen, wenn man mit diesem Generator immer einen Zwilling konstruieren könnte, so dass zumindest eine der beiden Primzahlen des neuen Zwillings größer als p_(n+1) ist.

Nochmal EDIT: Mit einem kleinen Computerprogramm kann man zeigen, dass man mit allen Möglichkeiten an Exponenten, ähnlich auch wie im verlinkten MatheBoard-Thema beschrieben + Beschreibung aus dem WP-Artikel, aus den Zahlen 2 und 3 alle Primzahlen kleiner 5²-1 und aus den Zahlen 2, 3 und 5 alle Primzahlen kleiner als 7²-1 konstruieren kann.

Im ersten Fall kann man die Exponenten der Zahlen 2 und 3 von 1 bis 5 variieren und jeweils die Summe und Differenz betrachten.

Im zweiten Fall reicht es die Exponenten auch bis maximal 5 zu betrachten. Man hat dann die Kombinationen 2^i + 3^j * 5^k, 2^i - 3^j * 5^k, 2^i * 3^j + 5^k und 2^i * 3^j - 5^k, wobei die Exponenten i, j, und k immer von 1 bis 5 laufen und das Ergebnis nur gespeichert wird, falls es im Bereich 2 bis 47 liegt.

Das macht den Generator interessant, weil man damit eventuell aus einer vorher bekannten vollständigen Menge an Primzahlen eine größere vollständige Menge an Primzahlen ableiten kann.

Für die konkrete Anwendung in einem Computerprogramm ist dieser Generator aufgrund der hohen Anzahl an Kombinationen in den Exponenten aber leider nur für sehr kleine Mengen an Primzahlen anwendbar. Bereits bei der Schranke von 1e6 ist das Sieb des Eratosthenes im Rechenaufwand deutlich geringer.
__________________
Freundliche Grüße, B.

Ge?ndert von Bernhard (22.11.21 um 19:49 Uhr)
Mit Zitat antworten