Perrin-Folge

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

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 <math>P(n)</math> die Anzahl der 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:

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, Primzahlen. 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 Pseudoprimzahlen. Die kleinste Perrinsche Pseudoprimzahl ist 271441=521², 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.<ref>{{#invoke:Vorlage:Literatur|f}}{{#if:

       | {{#if: Vorlage:Cite book/ParamBool
               | Vorlage:Toter Link/archivebot
               | Vorlage:Webarchiv/archiv-bot
         }}
  }}{{#invoke:TemplatePar|check
   |all    = title=
   |opt    = vauthors= author= author1= authorlink= author-link= author-link1= author1-link= author2= author3= author4= author5= author6= author7= author8= author9= editor= last= first= last1= first1= last2= first2= last3= first3= last4= first4= last5= first5= last6= first6= last7= first7= last8= first8= last9= first9= last10= first10= last11= first11= last12= first12= last13= first13= last14= first14= last15= first15= others= script-title= trans-title= date= year= volume= issue= number= series= page= pages= at= issn= arxiv= bibcode= doi= pmid= pmc= jstor= oclc= id= url= url-status= format= access-date= archive-date= archive-url= archivebot= offline= location= publisher= language= quote= work= journal= newspaper= magazine= periodical=  name-list-style= url-access= doi-access= display-authors= via= s2cid= mr= type= citeseerx=  accessdate= archivedate= archiveurl= coauthors= month= day= last16= first16= last17= first17= last18= first18= last19= first19= last20= first20= last21= first21= last22= first22= last23= first23= last24= first24= last25= first25= last26= first26= last27= first27= last28= first28= last29= first29= last30= first30= last31= first31=
   |cat      = Wikipedia:Vorlagenfehler/Vorlage:Cite journal
   |errNS    = 0
   |template = Vorlage:Cite journal
   |format   = @@@
   |preview  = 1
  }}Vorlage:Cite book/URL{{#if:  | Vorlage:Cite book/Meldung }}{{#if:        | Vorlage:Cite book/Meldung }}{{#if: Journal of Number Theory
     || Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
        | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
       | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}Vorlage:Cite book/Meldung2{{#ifexpr: 0{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:Jon Grantham|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }} (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, … (Folge A074788 in OEIS)

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, … (Folge A112881 in OEIS)

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

Vorlage:Navigationsleiste Primzahlklassen