Perrin-Folge

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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[Bearbeiten]

Die Glieder der Perrin-Folge werden wie folgt definiert:

P_n = P_{n-2} + P_{n-3}
P0 = 3
P1 = 0
P2 = 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[Bearbeiten]

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=5212. Es gibt unendlich viele Perrinsche Pseudoprimzahlen.[1]

Einzelnachweise[Bearbeiten]

  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)