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:
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:
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.