Die Perrin Folge ist eine Folge naturlicher Zahlen bei der ahnlich wie bei der Fibonacci Folge jedes Glied die Summe von Vorgangergliedern ist also eine rekursiv definierte Folge Die einzelnen Folgenglieder nennt man Perrin Zahl Inhaltsverzeichnis 1 Geschichte 2 Definition 3 Teilbarkeitseigenschaften 4 Perrin Primzahlen 5 Siehe auch 6 EinzelnachweiseGeschichte Bearbeiten1876 arbeitete Edouard Lucas an einer Folge mit der Bildungsregel P n P n 2 P n 3 displaystyle P n P n 2 P n 3 nbsp die jedoch andere Startwerte besass als die Perrin Folge 1899 entwickelte Raoul Perrin Ideen von Lucas weiter und stellte aus dessen Bildungsregel mit den Startwerten P 0 3 P 1 0 displaystyle P 0 3 P 1 0 nbsp und P 2 2 displaystyle P 2 2 nbsp eine Folge auf die als Perrin Folge bekannt wurde Definition BearbeitenDie Glieder der Perrin Folge werden wie folgt definiert P n P n 2 P n 3 displaystyle P n P n 2 P n 3 nbsp P 0 3 displaystyle P 0 3 nbsp P 1 0 displaystyle P 1 0 nbsp P 2 2 displaystyle P 2 2 nbsp 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 Folge A001608 in OEIS Sie spielt in der Graphentheorie eine Rolle da P n displaystyle P n nbsp die Anzahl der maximalen stabilen Mengen in einem zyklischen Graphen mit n displaystyle n nbsp Knoten ist Teilbarkeitseigenschaften BearbeitenIn der folgenden Tabelle sind die ersten 10 Folgenglieder aufgefuhrt fur die n displaystyle n nbsp ein Teiler von P n displaystyle P n nbsp ist n 2 3 5 7 11 13 17 19 23 29P n 2 3 5 7 22 39 119 209 644 3480Interessanterweise sind in dieser Tabelle alle n displaystyle n nbsp die P n displaystyle P n nbsp teilen Primzahlen Tatsachlich hat man bewiesen dass wenn n displaystyle n nbsp eine Primzahl ist n displaystyle n nbsp den Folgenwert P n displaystyle P n nbsp teilt Lasst sich der Schluss daraus ziehen dass wenn n displaystyle n nbsp den Folgenwert P n displaystyle P n nbsp teilt n displaystyle n nbsp eine Primzahl sein muss Nein es gibt auch zusammengesetzte n displaystyle n nbsp die P n displaystyle P n nbsp teilen Diese zusammengesetzten n displaystyle n nbsp 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 Perrin Primzahlen BearbeitenEine 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 Folge A074788 in OEIS Fur diese Perrin Primzahlen ist der Index n displaystyle n nbsp von P n displaystyle P n nbsp 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 Folge A112881 in OEIS Beispiel 1 Es ist P 9 12 displaystyle P 9 12 nbsp und P 10 17 displaystyle P 10 17 nbsp Somit ist P 12 P 10 P 9 17 12 29 P displaystyle P 12 P 10 P 9 17 12 29 in mathbb P nbsp eine Primzahl die sechstkleinste der ersten der beiden obigen Listen Tatsachlich taucht der Index n 12 displaystyle n 12 nbsp in obiger Liste an der 8 Stelle auf dd Beispiel 2 Nicht immer erhalt man mit obiger Liste unterschiedliche Perrin Primzahlen Zum Beispiel ist P 5 P 3 P 2 3 2 5 displaystyle P 5 P 3 P 2 3 2 5 nbsp und P 6 P 4 P 3 2 3 5 displaystyle P 6 P 4 P 3 2 3 5 nbsp gleich Auch P 2 2 displaystyle P 2 2 nbsp und P 4 P 2 P 1 2 0 2 displaystyle P 4 P 2 P 1 2 0 2 nbsp ergeben die gleiche Perrin Primzahl Diese beiden Primzahlen sind allerdings die einzigen die man mit obiger Indexliste mehrfach erhalt dd dd Siehe auch BearbeitenPadovan Folge mit gleicher RekursionEinzelnachweise Bearbeiten Jon Grantham There are infinitely many Perrin pseudoprimes In Journal of Number Theory 130 Jahrgang Nr 5 2010 S 1117 1128 doi 10 1016 j jnt 2009 11 008 els cdn com PDF PDF Datei 215 kB V DPrimzahl mengenformelbasiert Carol 2n 1 2 2 Doppelte Mersenne 22p 1 1 Fakultat n 1 Fermat 22n 1 Kubisch x3 y3 x y Kynea 2n 1 2 2 Leyland xy yx Mersenne 2p 1 Mills A3n Pierpont 2u 3v 1 Primorial pn 1 Proth k 2n 1 Pythagoreisch 4n 1 Quartisch x4 y4 Thabit 3 2n 1 Wagstaff 2p 1 3 Williams b 1 bn 1 Woodall n 2n 1 Primzahlfolgen Bell Fibonacci Lucas Motzkin Pell Perrineigenschaftsbasiert Elitar Fortunate Gut Glucklich Higgs Hochkototient Isoliert Pillai Ramanujan Regular Stark Stern Wall Sun Sun Wieferich Wilsonbasis abhangig Belphegor Champernowne Dihedral Einzigartig Frohlich Keith Lange Minimal Mirp Permutierbar Primeval Palindrom Repunit Primzahl 10n 1 9 Schwach Smarandache Wellin Strobogrammatisch Tetradisch Trunkierbar Zirkularbasierend auf Tupel Ausbalanciert p n p p n Chen Cousin p p 4 Cunningham p 2p 1 Drilling p p 2 oder p 4 p 6 Konstellation Sexy p p 6 Sichere p p 1 2 Sophie Germain p 2p 1 Vierling p p 2 p 6 p 8 Zwilling p p 2 Zwillings Bi Kette n 1 2n 1 nach Grosse Titanisch 1 000 Stellen Gigantisch 10 000 Stellen Mega 1 000 000 Stellen Beva 1 000 000 000 Stellen Abgerufen von https de wikipedia org w index php title Perrin Folge amp oldid 239249193 Perrin Primzahlen
