Perrin-számok
A matematika, azon belül a számelmélet területén a Perrin-számok a következő rekurzív megadású sorozattal meghatározott számok:

 minden -re,
a kezdeti értékek pedig
.

A Perrin-számok sorozata így kezdődik:
3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39 ... 

Az -csúcsú körgráfok különböző maximális független csúcshalmazainak száma éppen az -edik Perrin-számmal egyenlő (ha ).

Története
A sorozatot elsőként Édouard Lucas említette 1876-ban. 1899-ben ugyanezzel a sorozattal François Olivier Raoul Perrin foglalkozott. A legátfogóbb vizsgálatot Adams és Shanks (1982) végezte el a sorozattal kapcsolatban.

Tulajdonságai

Generátorfüggvény
A Perrin-sorozat generátorfüggvénye:

Mátrixformula

Binet-féle formula

A Perrin-sorozat számai felírható a következő egyenlet gyökeinek hatványai segítségével:

Az egyenletnek három gyöke van; egy p valós gyöke (az úgynevezett műanyagszám, plastic number) és a két komplex konjugált gyök, q és r. Ezt a három gyököt tekintve a Lucas-sorozat Binet-formulájának analógiájára a Perrin-sorozat Binet-formulája:

Mivel a q és r komplex gyökök egynél kisebbek, nagy n-re ezek hatványai nullához közelítenek. Nagy n-re tehát a képlet így is felírható:

Ennek segítségével gyorsan kiszámíthatók a Perrin-sorozat tagjai nagy n-ekre. A Perrin-sorozat egymást követő tagjainak aránya közelít p-hez, aminek értéke körülbelül 1,324718. Ez a konstans ugyanaz a Perrin-sorozat számára, mint az aranymetszés Φ-je a Lucas-sorozat számára. Hasonló kapcsolat létezik p és a Padovan-sorozat, a Φ és a Fibonacci-számok, illetve az ezüstmetszés arányszáma és a Pell-számok között.

Szorzási formula
A Binet-formulából meghatározható G(kn) képlete G(n−1), G(n) és G(n+1)-ből kifejezve; tudjuk, hogy

ami három lineáris egyenletet eredményez, melynek együtthatói  felbontási testjében vannak; egy mátrixinverzióval megoldható az egyenletrendszer -re, majd a k-adik hatványra emelve kiszámítható az összeg.

Magma példakód:

 P<x> := PolynomialRing(Rationals());
 S<t> := SplittingField(x^3-x-1);
 P2<y> := PolynomialRing(S);
 p,q,r := Explode([r[1] : r in Roots(y^3-y-1)]);
 Mi:=Matrix([[1/p,1/q,1/r],[1,1,1],[p,q,r]])^(-1);
 T<u,v,w> := PolynomialRing(S,3);
 v1 := ChangeRing(Mi,T) *Matrix([[u],[v],[w]]);
 [p^i*v1[1,1]^3 + q^i*v1[2,1]^3 + r^i*v1[3,1]^3 : i in [-1..1]];

melynek eredménye az  helyettesítésekkel:

A 23-as szám itt a sorozatot meghatározó polinomból adódik.

Az előzőek alkalmazásával kiszámítható az n-edik Perrin-szám egész aritmetika és  darab szorzás segítségével.

Prímszámok és oszthatóság

Perrin-álprímek

Bebizonyították, hogy minden minden p prímre, p osztója P(p)-nek. Az állítás megfordítása azonban nem igaz: egyes n összetett számokra is n osztója P(n)-nek. Ha n ezzel a ritka tulajdonsággal rendelkezik, akkor Perrin-álprím.

Az első néhány Perrin-álprím:
271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431, ... 

A Perrin-álprímek létezésének kérdése már Perrinben is felmerült, de létezésükről nem tudott senki, míg Adams and Shanks (1982) felfedezték a legkisebbet, a 271441 = 5212 számot; a következő legkisebb a 904631 = 7 · 13 · 9941. Tizenhét egymilliárdnál kisebb Perrin-álprím létezik; Jon Grantham bebizonyította, hogy végtelen sok létezik belőlük.

Adams and Shanks (1982) azt is észrevették, hogy a prímek eleget tesznek a következő feltételnek: P(−p) = −1 mod p. Az olyan összetett számok, amik mindkét feltételnek megfelelnek, a szigorú Perrin-álprímek (Restricted Perrin pseudoprimes) . További feltételek képezhetők az n hat előjeléből, melyek három különböző formát vehetnek fel.

Bár a Perrin-féle álprímek ritkák, jelentős átfedés van köztük és a Fermat-álprímek között. Ez éles ellentétben van a Lucas-álprímekkel, melyek antikorrelálnak. Ez utóbbi jelenség teszi lehetővé a népszerű és igen hatásos Baillie–PSW-prímteszt működését, melynél nem ismeretesek álprímek, de ha léteznek, biztosan nagyobbak 264-nél.

Perrin-prímek
A Perrin-prímek olyan Perrin-számok, melyek prímszámok. Az első néhány Perrin-prím:

2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797, ... 

A Perrin-prímekhez tartozó indexek a Perrin-sorozatban, tehát a -ekhez tartozó  számok:
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, ...

Jegyzetek

Fordítás

További információk
Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence
MathPages - Lucas Pseudoprimes
MathPages - Perrin's Sequence
Perrin-like sequence

Nevezetes számsorozatok