Perrin-Folge

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

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

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

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

n2357111317192329
P(n)235722391192096443480

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

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

  • Padovan-Folge mit gleicher Rekursion

Einzelnachweise

  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)