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:

Sablon:Math minden Sablon:Math-re,

a kezdeti értékek pedig

Sablon:Math.

A Perrin-számok sorozata így kezdődik:

3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39 ... Sablon:OEIS

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

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:

$G(P(n);x)=\frac{3-x^2}{1-x^2-x^3}.$

Mátrixformula

${\left(\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 1& 0\end{array}\right)}^n\left(\begin{array}{c}3\\ 0\\ 2\end{array}\right)=\left(\begin{array}{c}P\left(n\right)\\ P(n+1)\\ P(n+2)\end{array}\right)$

Binet-féle formula

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

$x^3-x-1=0.$

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:

$P\left(n\right)=p^n+q^n+r^n.$

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ó:

$P\left(n\right)\approx p^n$

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

$\begin{array}{ccccc}G(n-1)& =& p^{-1}{p}^n+& q^{-1}{q}^n+& r^{-1}{r}^n\\ G(n)& =& p^n+& q^n+& r^n\\ G(n+1)& =& p{p}^n+& q{q}^n+& r{r}^n\end{array}$

ami három lineáris egyenletet eredményez, melynek együtthatói $x^3-x-1$ felbontási testjében vannak; egy mátrixinverzióval megoldható az egyenletrendszer $p^n,q^n,r^n$-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 $u=G(n-1),v=G(n),w=G(n+1)$ helyettesítésekkel:

$\begin{array}{ccc}23G(2n-1)& =& 4u^2+3v^2+9w^2+18uv-12uw-4vw\\ 23G(2n)& =& -6u^2+7v^2-2w^2-4uv+18uw+6vw\\ 23G(2n+1)& =& 9u^2+v^2+3w^2+6uv-4uw+14vw\\ 23G(3n-1)& =& (-4u^3+2v^3-w^3+9(u{v}^2+v{w}^2+w{u}^2)+3v^{2}w+6uvw)\\ 23G(3n)& =& (3u^3+2v^3+3w^3-3(u{v}^2+u{w}^2+v{w}^2+v{u}^2)+6v^{2}w+18uvw)\\ 23G(3n+1)& =& (v^3-w^3+6u{v}^2+9u{w}^2+6v{w}^2+9v{u}^2-3w{u}^2+6w{v}^2-6uvw)\end{array}$

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 $O(\log n)$ 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, ... Sablon:OEIS

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 = 521² 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) Sablon:OEIS. 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 2⁶⁴-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, ... Sablon:OEIS

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

Jegyzetek

• Sablon:Cite journal

• Sablon:Cite journal

• Sablon:Cite book
• Sablon:Cite journal

• Sablon:Cite journal

Fordítás

• Sablon: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