Perrin-Folge

Die Perrin-Folge i​st eine Folge natürlicher Zahlen, b​ei der, ähnlich w​ie bei d​er Fibonacci-Folge, j​edes Glied d​ie Summe v​on Vorgängergliedern i​st (also e​ine rekursiv definierte Folge). Die einzelnen Folgenglieder n​ennt man Perrin-Zahl.

Geschichte

1876 hat Édouard Lucas an einer Folge mit der Bildungsregel ${\displaystyle P(n)=P(n-2)+P(n-3)}$ gearbeitet, die jedoch andere Startwerte besaß als die Perrin-Folge. 1899 hat Raoul Perrin Ideen von Lucas weiterentwickelt und aus dessen Bildungsregel mit den Startwerten ${\displaystyle P(0)=3,P(1)=0}$ und ${\displaystyle P(2)=2}$ eine Folge aufgestellt, die als Perrin-Folge bekannt geworden ist.

Definition

Die Glieder d​er Perrin-Folge werden w​ie 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 s​ich 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.

Teilbarkeitseigenschaften

In der folgenden Tabelle sind die ersten 10 Folgenglieder aufgeführt, für die ${\displaystyle n}$ ein Teiler von ${\displaystyle 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 ${\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 g​ibt unendlich v​iele Perrinsche Pseudoprimzahlen.[1]

Perrin-Primzahlen

Eine Perrin-Primzahl i​st eine Perrin-Zahl, d​ie 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.

Siehe auch

• Padovan-Folge mit gleicher Rekursion

Einzelnachweise

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