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.

1876 arbeitete Édouard Lucas an einer Folge mit der Bildungsregel ${\displaystyle P(n)=P(n-2)+P(n-3)}$, 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 ${\displaystyle P(0)=3,P(1)=0}$ und ${\displaystyle P(2)=2}$ eine Folge auf, die als Perrin-Folge bekannt wurde.

Die Glieder der Perrin-Folge werden wie folgt definiert:

${\displaystyle P_{n}=P_{n-2}+P_{n-3}}$

${\displaystyle P_{0}=3}$

${\displaystyle P_{1}=0}$

${\displaystyle P_{2}=2}$

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 ${\displaystyle P(n)}$ die Anzahl der maximalen stabilen Mengen in einem zyklischen Graphen mit ${\displaystyle n}$ Knoten ist.

In der folgenden Tabelle sind die ersten 10 Folgenglieder aufgeführt, für die ${\displaystyle n}$ ein Teiler von ${\displaystyle P(n)}$ ist:

Interessanterweise sind in dieser Tabelle alle ${\displaystyle n}$, die ${\displaystyle P(n)}$ teilen, Primzahlen. Tatsächlich hat man bewiesen, dass, wenn ${\displaystyle n}$ eine Primzahl ist, ${\displaystyle n}$ den Folgenwert ${\displaystyle P(n)}$ teilt. Lässt sich der Schluss daraus ziehen, dass, wenn ${\displaystyle n}$ den Folgenwert ${\displaystyle P(n)}$ teilt, ${\displaystyle n}$ eine Primzahl sein muss? Nein, es gibt auch zusammengesetzte ${\displaystyle n}$, die ${\displaystyle P(n)}$ teilen. Diese zusammengesetzten ${\displaystyle n}$ nennt man Perrinsche Pseudoprimzahlen. Die kleinste Perrinsche Pseudoprimzahl ist 271441=521², 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]

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 ${\displaystyle n}$ von ${\displaystyle P(n)}$ 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 ${\displaystyle P(9)=12}$ und ${\displaystyle P(10)=17}$. Somit ist ${\displaystyle P(12)=P(10)+P(9)=17+12=29\in \mathbb {P} }$ eine Primzahl (die sechstkleinste der ersten der beiden obigen Listen). Tatsächlich taucht der Index ${\displaystyle n=12}$ in obiger Liste an der 8. Stelle auf.

Beispiel 2:

Nicht immer erhält man mit obiger Liste unterschiedliche Perrin-Primzahlen. Zum Beispiel ist ${\displaystyle P(5)=P(3)+P(2)=3+2=5}$ und ${\displaystyle P(6)=P(4)+P(3)=2+3=5}$ gleich. Auch ${\displaystyle P(2)=2}$ und ${\displaystyle P(4)=P(2)+P(1)=2+0=2}$ ergeben die gleiche Perrin-Primzahl. Diese beiden Primzahlen sind allerdings die einzigen, die man mit obiger Indexliste mehrfach erhält.

• Padovan-Folge mit gleicher Rekursion

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)