Die Perrin-Folge ist eine Folge natürlicher Zahlen, bei der, ähnlich wie bei der Fibonacci-Folge, jedes Glied die Summe von Vorgängergliedern ist (also eine rekursiv definierte Folge). Die einzelnen Folgenglieder nennt man Perrin-Zahl.

Geschichte

Bearbeiten

1876 arbeitete Édouard Lucas an einer Folge mit der Bildungsregel  , die jedoch andere Startwerte besaß als die Perrin-Folge. 1899 entwickelte Raoul Perrin Ideen von Lucas weiter und stellte aus dessen Bildungsregel mit den Startwerten   und   eine Folge auf, die als Perrin-Folge bekannt wurde.

Definition

Bearbeiten

Die Glieder der Perrin-Folge werden wie folgt definiert:

 
 
 
 

Daraus ergibt sich die Folge:

3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, 209, 277, 367, 486, 644, 853, 1130, 1497, 1983, 2627, 3480, 4610, 6107, 8090, 10717, 14197, 18807, 24914, 33004, 43721, 57918, 76725, 101639, 134643, 178364, 236282, 313007, … (Folge A001608 in OEIS)

Sie spielt in der Graphentheorie eine Rolle, da   die Anzahl der maximalen stabilen Mengen in einem zyklischen Graphen mit   Knoten ist.

Teilbarkeitseigenschaften

Bearbeiten

In der folgenden Tabelle sind die ersten 10 Folgenglieder aufgeführt, für die   ein Teiler von   ist:

n 2 3 5 7 11 13 17 19 23 29
P(n) 2 3 5 7 22 39 119 209 644 3480

Interessanterweise sind in dieser Tabelle alle  , die   teilen, Primzahlen. Tatsächlich hat man bewiesen, dass, wenn   eine Primzahl ist,   den Folgenwert   teilt. Lässt sich der Schluss daraus ziehen, dass, wenn   den Folgenwert   teilt,   eine Primzahl sein muss? Nein, es gibt auch zusammengesetzte  , die   teilen. Diese zusammengesetzten   nennt man Perrinsche Pseudoprimzahlen. Die kleinste Perrinsche Pseudoprimzahl ist 271441=5212, die zweitkleinste ist 904631=7·13·9941. Die ersten Perrinschen Pseudoprimzahlen sind die folgenden:

271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431, 1091327579, 1133818561, 1235188597, 1389675541, … (Folge A013998 in OEIS)

Es gibt unendlich viele Perrinsche Pseudoprimzahlen.[1]

Perrin-Primzahlen

Bearbeiten

Eine Perrin-Primzahl ist eine Perrin-Zahl, die prim ist. Die kleinsten Perrin-Primzahlen lauten:

2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797, 22584751787583336797527561822649328254745329, … (Folge A074788 in OEIS)

Für diese Perrin-Primzahlen ist der Index   von   der folgende:

2, 3, 4, 5, 6, 7, 10, 12, 20, 21, 24, 34, 38, 75, 122, 166, 236, 355, 356, 930, 1042, 1214, 1461, 1622, 4430, 5802, 9092, 16260, 18926, 23698, 40059, 45003, 73807, 91405, 263226, 316872, 321874, 324098, 581132, … (Folge A112881 in OEIS)
Beispiel 1:
Es ist   und  . Somit ist   eine Primzahl (die sechstkleinste der ersten der beiden obigen Listen). Tatsächlich taucht der Index   in obiger Liste an der 8. Stelle auf.
Beispiel 2:
Nicht immer erhält man mit obiger Liste unterschiedliche Perrin-Primzahlen. Zum Beispiel ist   und   gleich. Auch   und   ergeben die gleiche Perrin-Primzahl. Diese beiden Primzahlen sind allerdings die einzigen, die man mit obiger Indexliste mehrfach erhält.

Siehe auch

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Jon Grantham: There are infinitely many Perrin pseudoprimes. In: Journal of Number Theory. 130. Jahrgang, Nr. 5, 2010, S. 1117–1128, doi:10.1016/j.jnt.2009.11.008 (els-cdn.com [PDF]). (PDF-Datei; 215 kB)