Quelltext der Seite Perrin-Folge

Die '''Perrin-Folge''' ist eine [[Zahlenfolge|Folge]] natürlicher Zahlen, bei der, ähnlich wie bei der [[Fibonacci-Folge]], jedes Glied die Summe von Vorgängergliedern ist (also eine [[Rekursion|rekursiv]] definierte Folge). Die einzelnen Folgenglieder nennt man '''Perrin-Zahl'''.

== Geschichte ==
1876 arbeitete [[Édouard Lucas]] an einer Folge mit der Bildungsregel <math>P(n) = P(n-2) + P(n-3)</math>, 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 <math>P(0) = 3, P(1) = 0</math> und <math>P(2) = 2</math> eine Folge auf, die als ''Perrin-Folge'' bekannt wurde.

== Definition ==
Die Glieder der Perrin-Folge werden wie folgt definiert:
: <math>P_n = P_{n-2} + P_{n-3}</math>
: <math>P_0 = 3</math>
: <math>P_1 = 0</math>
: <math>P_2 = 2</math>

Daraus ergibt sich die Folge:
: 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, 209, 277, 367, 486, 644, 853, 1130, 1497, 1983, 2627, 3480, 4610, 6107, 8090, 10717, 14197, 18807, 24914, 33004, 43721, 57918, 76725, 101639, 134643, 178364, 236282, 313007, … ({{OEIS|A001608}})
Sie spielt in der [[Graphentheorie]] eine Rolle, da <math>P(n)</math> die Anzahl der [[stabile Menge|maximalen stabilen Mengen]] in einem zyklischen Graphen mit <math>n</math> Knoten ist.

== Teilbarkeitseigenschaften ==
In der folgenden Tabelle sind die ersten 10 Folgenglieder aufgeführt, für die <math>n</math> ein Teiler von <math>P(n)</math> ist:

{| class="wikitable"
|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 <math>n</math>, die <math>P(n)</math> teilen, [[Primzahl]]en. Tatsächlich hat man bewiesen, dass, wenn <math>n</math> eine Primzahl ist, <math>n</math> den Folgenwert <math>P(n)</math> teilt. 
Lässt sich der Schluss daraus ziehen, dass, wenn <math>n</math> den Folgenwert <math>P(n)</math> teilt, <math>n</math> eine Primzahl sein muss? Nein, es gibt auch zusammengesetzte <math>n</math>, die <math>P(n)</math> teilen. Diese zusammengesetzten <math>n</math> nennt man '''Perrinsche [[Pseudoprimzahl]]en'''. Die kleinste Perrinsche Pseudoprimzahl ist 271441=521<sup>2</sup>, 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, … ({{OEIS|A013998}})
Es gibt unendlich viele Perrinsche Pseudoprimzahlen.<ref>{{cite journal |author=Jon Grantham |date=2010 |title=There are infinitely many Perrin pseudoprimes |journal=Journal of Number Theory |volume=130 |issue=5 |pages=1117–1128 |doi=10.1016/j.jnt.2009.11.008 |url=http://ac.els-cdn.com/S0022314X10000120/1-s2.0-S0022314X10000120-main.pdf?_tid=cb164bc2-614e-11e6-801e-00000aab0f26&acdnat=1471090352_37ef9bb6030a3019131469124758afdb |language=en}} (PDF-Datei; 215 kB)</ref>

== Perrin-Primzahlen ==
Eine '''Perrin-Primzahl''' ist eine Perrin-Zahl, die prim ist. Die kleinsten Perrin-Primzahlen lauten:
: 2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797, 22584751787583336797527561822649328254745329, … ({{OEIS|A074788}})
Für diese Perrin-Primzahlen ist der Index <math>n</math> von <math>P(n)</math> der folgende:
: 2, 3, 4, 5, 6, 7, 10, 12, 20, 21, 24, 34, 38, 75, 122, 166, 236, 355, 356, 930, 1042, 1214, 1461, 1622, 4430, 5802, 9092, 16260, 18926, 23698, 40059, 45003, 73807, 91405, 263226, 316872, 321874, 324098, 581132, … ({{OEIS|A112881}})
:: '''Beispiel 1:'''
::: Es ist <math>P(9)=12</math> und <math>P(10)=17</math>. Somit ist <math>P(12)=P(10)+P(9)=17+12=29 \in \mathbb P</math> eine Primzahl (die sechstkleinste der ersten der beiden obigen Listen). Tatsächlich taucht der Index <math>n=12</math> in obiger Liste an der 8. Stelle auf.
:: '''Beispiel 2:'''
::: Nicht immer erhält man mit obiger Liste unterschiedliche Perrin-Primzahlen. Zum Beispiel ist <math>P(5)=P(3)+P(2)=3+2=5</math> und <math>P(6)=P(4)+P(3)=2+3=5</math> gleich. Auch <math>P(2)=2</math> und <math>P(4)=P(2)+P(1)=2+0=2</math> ergeben die gleiche Perrin-Primzahl. Diese beiden Primzahlen sind allerdings die einzigen, die man mit obiger Indexliste mehrfach erhält.

== Siehe auch ==
* [[Padovan-Folge]] mit gleicher Rekursion

== Einzelnachweise ==
<references />

{{Navigationsleiste Primzahlklassen}}

[[Kategorie:Folge ganzer Zahlen]]
[[Kategorie:Ganzzahlmenge]]
[[Kategorie:Primzahl]]
[[Kategorie:Zahlentheorie]]