Primzahlfolgen:   Klassifzierung  und  Sätze

Einführung

Es gibt unendlich viele Primzahlen.   Die Folge aller Primzahlen ist deshalb unendlich.
Man kann aus ihr (unendlich oder endlich lange) Teilfolgen auswählen.

Dafür gibt es 3 Haupt-Prinzipien:


        Auswahl nach Index-Abstand     (Index := Primzahl-Nr.)
           "     "    Wert-Abstand
           "     "   Eigenschaften




Primzahlfolgen  mit  Index-Abständen

Alle Primzahlfolgen mit Index-Abständen sind prinzipiell unendlich lang, weil zu jedem Index eine Primzahl existiert. Siehe die folgenden Beispiele


Konstante Index-Abstände:

Beispiele:


  2  3  5  7  11  13  17  19  23  ...     alle Primzahlen
  2     5     11      17      23  ...    jede 2. Primzahl
  2        7          17          ...    jede 3. Primzahl
  2           11              23  ...    jede 4. Primzahl

Man erkennt:
- Von 2 Folgen mit Abstand d1 und d2 (d1 < d2), die bei derselben Primzahl beginnen, ist die 1. Folge genau dann eine Obermenge der 2. Folge, wenn d1 ein Teiler von d2 ist (Beispiel: oben die Folgen mit Index-Abstand 2 und 4)

- Allgemein gilt:   2 Folgen, die bei derselben Primzahl beginnen, haben einige gemeinsame Folgeglieder (auch wenn d1 kein Teiler von d2 ist), nämlich alle Primzahlen mit dem Index:

      Startindex + n*kgV(d1,d2)   mit n = 0,1,2,...
(Beispiel: oben die 2 Folgen mit Index-Abstand 2 und 3 haben die Startzahl 2 sowie jede 6. Primzahl gemeinsam). Die Durchschnittsfolge enthält also genau die Primzahlen mit diesen Indizes.
Der anfangs erwähnte Fall "d1 teilt d2" ist nur ein Sonderfall dieser Formel.



Man kann eine Folge mit Index-Abstand d bei jeder beliebigen Primzahl beginnen lassen.
Es gibt also zu jedem Abstand d unendlich viele Folgen.   Beispiele mit d=2:

  2  3  5  7  11  13  17  19  23  ...     alle Primzahlen
  2     5     11      17      23  ...     d=2,  ab 2  (1. Primzahl)
     3     7      15      19      ...     d=2,  ab 3  (2. Primzahl)
        5     11      17      23  ...     d=2,  ab 5  (3. Primzahl)

Man erkennt:
- Eine Folge mit Abstand d ab Primzahl Px (x-te Primzahl) ist genau dann eine Obermenge der Folge mit gleichem Abstand d ab Primzahl Py (x < y), wenn y = x + n*d   (Beispiele oben ab 1. und 3. Primzahl, 3 = 1 + 1*2).   Die Folgen unterscheiden sich also nur im Anfangsteil, den die längere Folge zusätzlich hat.       Ist aber y ≠ x + n*d, dann haben beide Folgen keine gemeinsamen Glieder



Folgen mit verschiedenem Startwert und verschiedenem Index-Abstand treffen sich nach einigen Gliedern. Ab dann gilt das weiter oben Gesagte über Folgen mit gleichem Startwert.





Alternierende Index-Abstände:

Es sind auch Primzahlfolgen mit alternierenden Index-Abständen möglich.
Beispiel:


  2  3  5  7  11  13  17  19  23  29  31  ...     alle Primzahlen
  2     5         13      19          31  ...     jede 2./3. Primzahl





Zunehmende Index-Abstände:

Bei der Bildung zunehmender Index-Abstände sind der Fantasie keine Grenzen gesetzt.
Beispiele:


  2  3  5  7  11  13  17  19  23  29  31  ...     alle Primzahlen
  2  3     7          17              31  ...     additiv zunehmend, Summand 1
  2  3     7              19              ...     multplikativ zunehmend, Faktor 2
                                                  (2er-Potenzen als Abstände)
  2     5         13                  31  ...     Primzahlfolge als Abstände
  2  3  5     11          19              ...     Fibonaccizahlen als Abstände






Stochastische Index-Abstände:

Es sind auch Primzahlfolgen mit zufälligen Index-Abständen möglich, die durch einen Zufallsgenerator bestimmt werden. Die Abstände könnten dabei bestimmten statistischen Verteilungen genügen. Solche Primzahlfolgen könnten für die experimentelle Mathematik per Computer interessant sein.








Primzahlfolgen mit Wert-Abständen

Bei solchen Primzahlfolgen interessiert vor allem folgende Frage:
- Wie lang kann eine Primzahlfolge bei einem bestimmten Abstand sein?


Dazu folgende allgemeine Überlegung:

Der durchschnittliche Abstand zwischen 2 benachbarten Primzahlen wächst mit zunehmendem Zahlenwert, wenn auch langsam und unregelmäßig.   Er nähert sich dem Wert ln(N).   Daraus folgt:

- Eine Primzahlfolge mit festem Wert-Abstand d kann nie unendlich lang werden,
  weil irgendwann der   durchschnittliche Primzahlabstand > d   wird

- Es wurde allerdings 2004 bewiesen, daß es zu jedem N unendlich viele arithmetische Primzahlfolgen   der Länge N gibt.   Dabei muß aber die Schrittweite d entsprechend groß sein.
  Gegenüber diesem theoretischen Wissen ist die Kenntnis realer Primzahlfolgen extrem gering:
  Eine der längsten bekannten arithmetischen Primzahlfolgen hat nur 22 Glieder
  (aber eine Schrittweite > 4 Billionen)

- Eine Primzahlfolge kann nur dann (vielleicht) unendlich lang werden,   wenn ihr
  Wert-Abstand d zumindest so stark wächst wie der durchschnittliche Primzahlabstand

Das ist aber nur eine   schwache, undifferenzierte Beschränkung.
Für die meisten Folgentypen ergeben sich weit stärkere Limits:





Konstante Abstände:   (Arithmetische Primzahlfolgen)

Folgen von Primzahlen mit konstanten Wertabständen nennt man arithmetische Primzahlfolgen.
Beispiele:

   3 -  5 -  7                (Abstand 2)
   3 -  7 - 11                (Abstand 4)
   5 - 11 - 17 - 23 - 29      (Abstand 6)

- Obige Folgen lassen sich nicht verlängern
- Die letzten zwei Folgen enthalten nicht nur aufeinanderfolgende Primzahlen:
   bei   "3 - 7 - 11"   fehlt 5,   bei   "5 - 11 - 17 - 23 - 29"   fehlen 7, 13, 19





Konstante ungerade Abstände:

Alle Primzahlen außer 2 sind ungerade. Deshalb sind die Abstände zwischen Primzahlen gerade (weil ungerade - ungerade = gerade), nur der Abstand zwischen der 2 und anderen Primzahlen ist ungerade. Deshalb gilt:

- Primzahlfolgen mit ungeradem Abstand beginnen immer mit 2
- sie haben nur 2 Glieder
- eine Primzahlfolge mit ungeradem Abstand d existiert genau dann, wenn 2 + d prim ist

Beispiele:
   2 - 3            (Abstand 1)
   2 - 5            (Abstand 3)
   2 - 7            (Abstand 5)
   2 - 9            (Abstand 7)  keine Primzahlfolge, weil 9=3*3
   2 - 11           (Abstand 9)



Konstanter Abstand 2:

Von 3 aufeinanderfolgenden ungeraden Zahlen ist eine durch 3 teilbar.
Deshalb   können   Primzahlfolgen mit Abstand 2   nur 2 Glieder haben.
Ausnahme: die Folge 3 - 5 - 7 hat 3 Glieder,  denn 3 ist durch 3 teilbar, aber prim
Beispiele:

   3 - 5 - 7
   5 - 7
   11 - 13
   17 - 19
   71 - 73

Zwei Primzahlen im Abstand 2 nennt man auch Primzahlzwilling.
Ob es unendlich viele Primzahlzwillinge gibt, ist bis heute unklar.






Konstante gerade Abstände ≥ 4:

Eine Primzahlfolge mit festem Abstand d ≥ 4   kann höchstens d-1 Glieder   haben.   Beweis:

P1 sei die erste Primzahl der Folge.   Sie lässt sich in n Summanden (d-1) und einen Rest < d-1 zerlegen.   Für den Abstand d gilt ähnlich   d = (d-1) + 1   =   Summand (d-1) + Rest 1
Wir veranschaulichen das am Beispiel  d=6,  P1 hat Rest 2   mit  Perlenarithmetik:


       --------------------- P3 -----------------
       --------------- P2 ------------

       -------- P1 --------     -- d -     -- d -     -- d - 

       OOOOO ..... OOOOO xx     OOOOOx     OOOOOx     OOOOOx

Blöcke mit je (d-1) = 5 Perlen sind blau dargestellt, rot die Reste modulo (d-1) von P1 und d


Man erkennt leicht:
Mit jedem neuen Folgeglied, das durch Addition von d erzeugt wird, nimmt der Gesamt-Rest um 1 zu. Nach 3 Folgegliedern ist im Beispiel oben der Gesamtrest = d-1, somit ist das Folgeglied   P1 + d + d + d   durch   d-1   teilbar, also keine Primzahl.
Je geringer der Rest von P1 mod (d-1) ist, desto mehr Glieder können im Abstand d folgen, bis ein Glied durch d-1 teilbar ist. Bei Rest 0 ist erst nach d-1 Schritten ein folgendes Glied durch d-1 teilbar, bei Rest 1 nach d-2 Schritten, bei Rest 2 nach d-3 Schritten, usw.   Das lässt sich leicht in eine Formel fassen (r = Rest von P1, also P1 mod (d-1) ):
     Glied Nr. (d-r)  =   n*(d-1) + r    + (d-r-1)*d
                      =      "    + r    + (d-r-1)*(d-1) + (d-r-1)
                      =      "           + (d-r-1)*(d-1) + (d-1)
                      =   (d-1)*(n + d-r-1 + 1)
                      =   (d-1)*(n + d-r)
Also ist das Glied Nr. d-r durch d-1 teilbar

Die Anzahl primer Glieder beträgt also max. d-1 (Startwert P1 und d-2 Nachfolger)

Diese max. Anzahl d-1 Glieder wird nur erreicht, wenn der Rest von P1 = 0 ist, also P1 mod (d-1) = 0, also P1 durch d-1 teilbar. Dann kann P1 nur Primzahl sein, wenn P1 = d-1 . D.h. es gibt nur eine einzige Folge mit Abstand d und d-1 Gliedern.   Ansonsten sind max. d-2 Glieder möglich
Wir fassen die bisherigen Ergebnisse zusammen:


Satz 1:
1a)   Eine Primzahlfolge  mit festem Abstand   d ≥ 4   kann max.   d-2   Glieder haben
1b)   Nur die eine Folge ab Anfangswert  d-1   kann max.   d-1   Glieder haben



Beispiele:
- Eine Primzahlfolge mit Abstand d = 4 kann höchstens d-2 = 2 Glieder haben
   Ausnahme ist die Folge   3 - 7 - 11 , denn sie beginnt bei  d-1 = 3, kann also 3 Glieder haben
- Eine Primzahlfolge mit Abstand d = 6 kann höchstens d-2 = 4 Glieder haben
   Ausnahme ist die Folge   5 - 11 - 17 - 23 - 29 , sie beginnt bei  d-1 = 5, kann also 5 Glieder haben


Das ist ein leicht merkbarer Satz, aber nicht die strengste Aussage, die man über die Länge von arithmetischen Primzahlfolgen machen kann

Betrachten wir z.B. Folgen mit Abstand 12, so wissen wir durch obigen Satz,, daß solche Folgen nie mehr als 11 Glieder haben können. Wir könnten sie aber auch, statt Modulo 11, untersuchen Modulo 7 und würden dann mit obiger Methode feststellen, daß sie nicht mehr als 7 Glieder haben können. Oder wir untersuchen sie Modulo 5 und würden feststellen, daß sie nicht mehr als 5 Glieder haben können. Weil nämlich spätestens dann ein Glied durch 7 bzw. 5 teilbar ist
(Bei Moduln ≠ d-1 nimmt aber die Summe der Reste nicht mehr gleichmäßig zu. Beispiel: Bei einer Folge mit d=8 und P1 mod(5)=0 ergeben sich folgende Reste mod(5) der Folgeglieder:   0 - 3 - 1 - 4 - 2 - 0   Das hat aber keinen Einfluß auf die max. Anzahl Glieder)

Begrenzend auf die Anzahl Folgeglieder wirken aber nur Moduln, die keine Teiler (oder Teilerprodukte) des Abstands sind. Wenn wir z.B. Folgen mit Schrittweite d=12 untersuchen Modulo 2, 3, 4, 6, dann sehen wir, dass auch nach Addition von beliebig vielen Abständen d nie ein Glied durch 2, 3, 4, 6, teilbar ist. Denn z.B. wird zu P1 mit Modulrest r ≠ 3 immer ein Vielfaches von 3 hinzugefügt, deshalb haben P1 und P1+d und P1+d+d ... immer denselben Modulrest bzgl. 3

Daraus ergibt sich:
Entscheidend für die maximale Länge einer solchen Primzahlfolge ist die kleinste Zahl min, die kein Teiler von d ist.   Es gilt:
- Min ≤ d-1,   denn d-1 ist nie Teiler von d
- Min ist prim.   Denn wäre z.B. 15 kein Teiler von d, dann wäre auch ihr Primfaktor 3 oder 5 oder
  beide kein Teiler von d,   somit min=3 oder min=5
- Min ist ungerade.   Denn alle Primzahlen sind ungerade, außer der 2, aber die ist Teiler von d,
  wir reden ja über Folgen mit geradem Abstand d≥ 4


Satz 2:   (Verschärfung von Satz 1)
Def:   min := kleinste Zahl, die kein Teiler von d ist.     Es gilt:   min ≤ d-1, prim, ungerade
2a)   Eine Primzahlfolge  mit festem Abstand   d ≥ 4   kann max.   min-1   Glieder haben
2b)   Nur die eine Folge ab Anfangswert  min   kann max.   min   Glieder haben

Also:   Bei einer Primzahlfolge  mit festem Abstand   d ≥ 4   gilt:
            max. Anzahl Glieder   =   kleinster fehlender Primteiler   der Schrittweite





Umgekehrt lässt sich sofort folgender Schluß ziehen (was Georg Cantor schon 1861 getan hat):

Satz 3:   (Umkehrung von Satz 2)
        n sei gerade:
3a)   Eine Primzahlfolge kann nur dann n Glieder haben,
        wenn ihr Abstand d alle Primfaktoren ≤ n enthält

        Denn dann ist min ≥ n+1   und somit min-1 ≥ n

- Ihr Abstand muß also mindestens gleich der Primfakultät von n sein
- Er kann nur gleich der Primfakultät oder einem Vielfachen davon sein,
  weil andere Zahlen nicht alle diese Primfaktoren enthalten

3b)   Ist der Anfangswert < d,   dann kann die Folge auch n+1 Glieder haben






Die Primfaktoren, die Primfakultät und der kleinste fehlende Primfaktor einer Zahl d (und damit die max. Folgenlänge bei Abstand d) gehorchen alle drei nur der schwachen Kausalität:
Zwar haben gleiche Ursachen (hier gleiche Zahlen) gleiche Wirkung (hier Primfaktoren / Primfakultät), aber schon leicht verschiedene Ursachen (Zahlen) haben oft oft stark verschiedene Wirkungen.
Das zeigt folgende Tabelle für die geraden Zahlen 2 bis 20:


Abstand dPrimfaktorenPrimfakultätkleinster fehlender Primfaktor
= max. Folgenlänge
2223
42*22*33
62*32*3*55
82*2*22*3*5*73
102*5"3
122*2*32*3*5*7*115
142*72*3*5*7*11*133
162*2*2*2"3
182*3*32*3*5*7*11*13*175
202*2*52*3*7*11*13*17*193


Die Primfakultät ist dabei am wenigsten "chaotisch", da sie nur zunimmt, wenn auch sprunghaft






Zunehmende (gerade) Abstände:

Zunehmende Wert-Abstände bei Primzahlfolgen:   wir betrachten nur gerade Abstände, weil - wie bereits weiter vorne erwähnt - Folgen mit ungeraden Abständen höchstens 2 Glieder haben können



Additiv zunehmende Abstände:
Der Abstand wächst um einen festen Summanden   (minimal 2, immer gerade, natürlich ganzzahlig).
Typischerweise ist der erste Abstand gleich dem Summanden.   Beispiele

  5 - 7 - 11 - 17             (Summand 2, Abstände 2, 4, 6)
  3 - 7 - 13                    (Summand 2, Abstände 4, 6)

  11 - 13 - 17 - 23 - 31 - 41 - 53 - 67 - 83 - 101
  (Summand 2, Abstände 2, 4, 6, 8, 10, 12, 14, 16, 18)

  17 - 19 - 23 - 29 - 37 - 47 - 59 - 73 - 89 - 107 - 127 - 149 - 173 - 199 - 227 - 257
  (Summand 2, Abstände 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30)

  5 - 7 - 13 - 23 - 37
  (Summand 4, Abstände 2, 6, 10, 14)

Obige Folgen lassen sich nicht verlängern



Multiplikativ zunehmende Abstände:
Der Abstand wächst um einen festen Faktor   (minimal 2, natürlich ganzzahlig).
Typischerweise ist der erste Abstand gleich dem Faktor (nur möglich, wenn dieser gerade)


  5 - 7 - 11 - 19                              (Faktor 2, Abstände 2, 4, 8)
  11 - 13 - 17                                 (Faktor 2, Abstände 2, 4)
  17 - 19 - 23 - 31 - 47 - 79           (Faktor 2, Abstände 2, 4, 8, 16, 32)
  41 - 43 - 47                                 (Faktor 2, Abstände 2, 4)

Obige Folgen lassen sich nicht verlängern

Prinzipiell sind aber - wie bereits weiter vorne erwähnt - bei nicht allzu langsam zunehmenden Abständen unendliche Primzahlfolgen möglich:   Der Wert-Abstand d muß zumindest so stark wachsen wie der durchschnittliche Primzahlabstand   ln(N)







Folgen von Primzahlen mit bestimmten Eigenschaften

Man wählt alle Primzahlen aus (optional erst ab einem bestimmten Startwert), die eine bestimmte Eigenschaft haben.

Allerdings ist es für Primzahlen charakteristisch, dass sie wenige Eigenschaften haben (wie z.B. Teilbarkeit durch eine bestimmte Zahl).   Man bezieht sich deshalb besser auf die vorangehende (oder noch weiter vorn, oder dahinter liegende) Zahl.     Eine Auswahlregel könnte z.B. lauten:
  "Nimm alle Primzahlen, deren Vorgänger-Zahl durch 3 teilbar ist."


  2  3  5  7  11  13  17  19  23  29  31  ...     alle Primzahlen
           7      13      19          31  ...     Vorgänger-Zahl
                                                  durch 3 teilbar

Es ergeben sich automatisch Primzahlabstände, die durch 3 teilbar sind. Sie sind auch durch 2 teilbar, weil alle Primzahlen (außer 2) ungerade und ihre Vorgängerzahlen deshalb gerade sind. Insgesamt sind also alle Primzahl-Wertabstände obiger Folge durch 6 teilbar.
Die ersten Abstände von 7 bis 103 sind:   6-6-12-6-6-18-6-6-6-18-6


Andere Auswahlregeln könnten lauten:
"Nimm alle Primzahlen > 100, deren Vor-Vorgänger-Zahl durch 19 teilbar ist"
"Nimm alle Primzahlen, deren Nachfolger-Zahl durch 3 oder 5 teilbar ist
(d.h. mit 15 einen gemeinsamen Teiler hat)"




Homepage  Leonhard Heinzmann                                      Stand: 8. 9. 2015