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 $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 $P(0)=3,P(1)=0$ und $P(2)=2$ eine Folge auf, die als Perrin-Folge bekannt wurde.

Definition

Die Glieder der Perrin-Folge werden wie folgt definiert:

$P_n=P_{n-2}+P_{n-3}$

$P_0=3$

$P_1=0$

$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, … (Vorlage:OEIS)

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

Teilbarkeitseigenschaften

In der folgenden Tabelle sind die ersten 10 Folgenglieder aufgeführt, für die $n$ ein Teiler von $P(n)$ 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 $n$, die $P(n)$ teilen, Primzahlen. Tatsächlich hat man bewiesen, dass, wenn $n$ eine Primzahl ist, $n$ den Folgenwert $P(n)$ teilt. Lässt sich der Schluss daraus ziehen, dass, wenn $n$ den Folgenwert $P(n)$ teilt, $n$ eine Primzahl sein muss? Nein, es gibt auch zusammengesetzte $n$, die $P(n)$ teilen. Diese zusammengesetzten $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, … (Vorlage:OEIS)

Es gibt unendlich viele Perrinsche Pseudoprimzahlen.

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, … (Vorlage:OEIS)

Für diese Perrin-Primzahlen ist der Index $n$ von $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, … (Vorlage:OEIS)

Beispiel 1:

Es ist $P(9)=12$ und $P(10)=17$. Somit ist $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 $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 $P(5)=P(3)+P(2)=3+2=5$ und $P(6)=P(4)+P(3)=2+3=5$ gleich. Auch $P(2)=2$ und $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.

Siehe auch

• Padovan-Folge mit gleicher Rekursion