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

GeschichteBearbeiten

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.

DefinitionBearbeiten

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.

TeilbarkeitseigenschaftenBearbeiten

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 auchBearbeiten

EinzelnachweiseBearbeiten

  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)