Perrin-Folge

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

Inhaltsverzeichnis

Geschichte

1876 hat Édouard Lucas an einer Folge mit der Bildungsregel P(n) = P(n − 2) + P(n − 3) gearbeitet, die jedoch andere Startwerte besaß, als die Perrin-Folge. 1899 hat R. Perrin Ideen von Lucas weiterentwickelt und aus dessen Bildungsregel mit den Startwerten P(0) = 3, P(1) = 0 und P(2) = 2 eine Folge aufgestellt, die als Perrin-Folge bekannt geworden ist.

Definition

Die Glieder der Perrin-Folge werden wie folgt definiert:

Pn = Pn − 2 + Pn − 3
P0 = 3
P1 = 0
P2 = 2

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

Teilbarkeitseigenschaften

In der folgenden Tabelle sind die ersten 10 Folgenglieder aufgeführt, für die n ein Teiler von P(n) 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 n, die P(n) teilen, Primzahlen. Tatsächlich hat man bewiesen, dass, wenn n eine Primzahl ist, n den Folgenwert P(n) teilt. Lässt sich der Schluss daraus ziehen, dass, wenn n den Folgenwert P(n) teilt, n eine Primzahl sein muss? Nein, es gibt auch zusammengesetzte n, die P(n) teilen. Diese zusammengesetzten n nennt man Perrinsche Pseudoprimzahlen (Folge A013998 in OEIS). Die kleinste Perrinsche Pseudoprimzahl ist 271441=5212. Es gibt unendlich viele Perrinsche Pseudoprimzahlen.[1]

Einzelnachweise

  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)

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Perrinsche Pseudoprimzahlen — Die Perrin Folge ist eine algebraische Zahlenfolge. Sie ist ähnlich der Fibonacci Folge eine rekursive Folge, bei der ein Glied dieser Folge die Summe von Vorgängergliedern ist. Inhaltsverzeichnis 1 Geschichte 2 Definition 3 Eigenschaften 4 …   Deutsch Wikipedia

  • Euklidisches Lemma — Eine Primzahl ist eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler, nämlich der Zahl 1 und sich selbst. Die kleinsten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 … (Folge A000040 in OEIS) Das Wort „Primzahl“ kommt aus… …   Deutsch Wikipedia

  • Primzahlen — Eine Primzahl ist eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler, nämlich der Zahl 1 und sich selbst. Die kleinsten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 … (Folge A000040 in OEIS) Das Wort „Primzahl“ kommt aus… …   Deutsch Wikipedia

  • Primzahl — Die Zahl 12 ist keine Primzahl. Eine Primzahl ist eine natürliche Zahl, die größer als eins und ausschließlich durch sich selbst und durch eins teilbar ist. Eine Primzahl ist also eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler …   Deutsch Wikipedia

  • Pseudoprimzahl — Eine Pseudoprimzahl ist eine zusammengesetzte, natürliche Zahl, die gewisse Eigenschaften mit Primzahlen gemeinsam hat, selbst aber keine Primzahl ist. Sie wird Pseudoprimzahl bezüglich dieser Eigenschaft genannt. Da es viele Möglichkeiten für… …   Deutsch Wikipedia

  • Vichy-Regime — État français Französischer Staat 1940–1944 …   Deutsch Wikipedia

  • Wayapopihíwi — 6.1208333333333 69.450277777778 Koordinaten: 6° 7′ 15″ N, 69° 27′ 1″ W …   Deutsch Wikipedia

  • Frank Riva — Filmdaten Deutscher Titel Frank Riva Produktionsland Frankreich, Deutschland …   Deutsch Wikipedia

  • Förster-Resonanzenergietransfer — Animation der abstandsabhängigen Energieübertragung von einem angeregten Donor auf einen Akzeptor über den Förstermechanismus. Der Förster Resonanzenergietransfer (kurz FRET), manchmal auch Fluoreszenz Resonanzenergietransfer genannt, ist ein… …   Deutsch Wikipedia

  • Château de Beaucastel — Flasche von Château de Beaucastel, Châteauneuf du Pape, AOC Das Château de Beaucastel ist eines der bedeutenden und traditionsreichen Weingüter der Appellation d’Origine Contrôlée (AOC) Châteauneuf du Pape der gleichnamigen Stadt im südlichen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”