Perrin-Folge
Die Perrin-Folge ist, ähnlich der Fibonacci-Folge eine rekursive Folge, bei der ein Glied dieser Folge die Summe von Vorgängergliedern ist.
Geschichte
1876 hat Edouard 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 Lucas Ideen weiterentwickelt, und aus Lucas 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 folgende Folge:
- 3 0 2 3 2 5 5 7 10 12 17 22 29 39 51 68 90 119 158 ...
Eigenschaften
Bestimmte n haben nun die Eigenschaft, P(n) zu teilen:
| 0 | 1 | 1 | 1 | 1 | 2 | 3 | 7 | 11 | 28 | 120 | 197 |
| P(n) | 0 | 2 | 3 | 5 | 7 | 22 | 39 | 119 | 209 | 644 | 3480 | 6107 |
| n | 1 | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 |
Interessanterweise sind alle n (in der Tabelle) die P(n) teilen, Primzahlen, mit Ausnahme von n=1. Tatsächlich hat man bewiesen, das wenn n eine Primzahl ist, n P(n) teilen muss. Läßt sich der Schluß daraus ziehen, daß wenn n 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
| perrinsche Pseudoprimzahlen | |
| 271441 | 521 * 521 |
| 904631 | 7 * 13 * 9941 |
| 16532714 | 2 * 11 * 11 * 53 * 1289 |
| 24658561 | 19 * 271 * 4789 |
| 27422714 | 2 * 11 * 11 * 47 * 2411 |
| 27664033 | 3037 * 9109 |
| 46672291 | 4831 * 9661 |
| 102690901 | 5851 * 17551 |
| 130944133 | 6607 * 19819 |
| 196075949 | 5717 * 34297 |
| 214038533 | 8447 * 25339 |
| 517697641 | 6311 * 82031 |
| 545670533 | 13487 * 40459 |
| 801123451 | 8951 * 89501 |
| 855073301 | 16883 * 50647 |
| 903136901 | 17351 * 52051 |
| 970355431 | 22027 * 44053 |