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

Geschichte

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

Definition

Die Glieder der Perrin-Folge werden wie folgt definiert:

P_n = P_{n − 2} + P_{n − 3}

P₀ = 3

P₁ = 0

P₂ = 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 ... (Folge A001608 in 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 (Folge A013998 in OEIS). Die kleinste Perrinsche Pseudoprimzahl ist 271441=521². Es gibt unendlich viele Perrinsche Pseudoprimzahlen.^[1]

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)