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:

P(n) = P(n − 2) + P(n − 3) minden n > 2-re,

a kezdeti értékek pedig

P(0) = 3, P(1) = 0, P(2) = 2.

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

3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39 ... (A001608 sorozat az OEIS-ben)

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

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.^[2] 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:

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

Mátrixformula

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

Binet-féle formula

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

${\displaystyle 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:

${\displaystyle 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ó:

${\displaystyle 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

${\displaystyle {\begin{matrix}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)&=&pp^{n}+&qq^{n}+&rr^{n}\end{matrix}}}$

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

${\displaystyle {\begin{matrix}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)&=&\left(-4u^{3}+2v^{3}-w^{3}+9(uv^{2}+vw^{2}+wu^{2})+3v^{2}w+6uvw\right)\\23G(3n)&=&\left(3u^{3}+2v^{3}+3w^{3}-3(uv^{2}+uw^{2}+vw^{2}+vu^{2})+6v^{2}w+18uvw\right)\\23G(3n+1)&=&\left(v^{3}-w^{3}+6uv^{2}+9uw^{2}+6vw^{2}+9vu^{2}-3wu^{2}+6wv^{2}-6uvw\right)\end{matrix}}}$

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 ${\displaystyle 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, ... (A013998 sorozat az OEIS-ben)

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;^[3] Jon Grantham bebizonyította,^[4] 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) (A018187 sorozat az OEIS-ben). 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, ... (A074788 sorozat az OEIS-ben)

A Perrin-prímekhez tartozó indexek a Perrin-sorozatban, tehát a P(n)-ekhez tartozó n 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, ... (A112881 sorozat az OEIS-ben)

Jegyzetek

1. (Füredi 1987)
2. (Knuth 2011)
3. (A013998 sorozat az OEIS-ben)
4. Jon Grantham (2010). „There are infinitely many Perrin pseudoprimes”. Journal of Number Theory 130 (5), 1117–1128. o. DOI:10.1016/j.jnt.2009.11.008.

• (1982) „Strong primality tests that are not sufficient”. Mathematics of Computation 39 (159), 255–300. o, Kiadó: American Mathematical Society. DOI:10.2307/2007637. JSTOR 2007637.

• Füredi, Z. (1987). „The number of maximal independent sets in connected graphs”. Journal of Graph Theory 11 (4), 463–470. o. DOI:10.1002/jgt.3190110403.

• The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley (2011). ISBN 0201038048
• Lucas, E. (1878). „Théorie des fonctions numériques simplement périodiques”. American Journal of Mathematics 1 (3), 197–240. o, Kiadó: The Johns Hopkins University Press. DOI:10.2307/2369311. JSTOR 2369311.

• Perrin, R. (1899). „Query 1484”. L'Intermédiaire des Mathématiciens 6, 76. o.

Fordítás

• Ez a szócikk részben vagy egészben a Perrin number című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

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