Perrin-Folge

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 | Quelltext bearbeiten]

1876 hat Édouard Lucas an einer Folge mit der Bildungsregel 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 und eine Folge aufgestellt, die als Perrin-Folge bekannt geworden ist.

Definition[Bearbeiten | Quelltext bearbeiten]

Die Glieder der Perrin-Folge werden wie folgt definiert:

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 die Anzahl der maximalen stabilen Mengen in einem zyklischen Graphen mit Knoten ist.

Teilbarkeitseigenschaften[Bearbeiten | Quelltext bearbeiten]

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:

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

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext 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)