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:

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

Mátrixformula

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

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

↑ (Füredi 1987)
↑ (Knuth 2011)
↑ (A013998 sorozat az OEIS-ben)
↑ 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

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

[1]

[2]

[3]

[4]

Sablon:Prímszámok osztályozása m v sz Prímszámok osztályozása
Képlet alapján	Fermat (2^2ⁿ + 1) Mersenne (2^p − 1) Dupla Mersenne (2^{2^p−1} − 1) Wagstaff (2^p + 1)/3 Proth (k·2ⁿ + 1) Faktoriális (n! ± 1) Primoriális (p_n# ± 1) Eukleidész (p_n# + 1) Pitagoraszi (4n + 1) Pierpont (2^u·3^v + 1) Kvartikus prímek (x⁴ + y⁴) Solinas (2^a ± 2^b ± 1) Cullen (n·2ⁿ + 1) Woodall (n·2ⁿ − 1) Köbös (x³ − y³)/(x − y) Carol (2ⁿ − 1)² − 2 Kynea (2ⁿ + 1)² − 2 Leyland (x^y + y^x) Szábit (3·2ⁿ ± 1) Mills (floor(A^3ⁿ))
Számsorozat alapján	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin Partíciók Bell Motzkin
Tulajdonság alapján	Wieferich (pár) Wall–Szun–Szun Wolstenholme Wilson Szerencsés Fortunátus Ramanujan Pillai Regular Erős Stern Szuperszinguláris (elliptikus) Szuperszinguláris (holdfény-elmélet) Jó Szuper Higgs Erősen kotóciens
Számrendszerfüggő	Boldog Diéder Palindrom Mírp Repunit (10ⁿ − 1)/9 Permutálható Körkörös Csonkolható Középpontosan tükrös Minimális Gyenge Full reptend Unikális Primeval Önös Smarandache–Wellin
Mintázatok	Iker (p, p + 2) Ikerprímlánc (n − 1, n + 1, 2n − 1, 2n + 1, …) Prímhármas (p, p + 2 vagy p + 4, p + 6) Prímnégyes (p, p + 2, p + 6, p + 8) prím n−es Unokatestvér (p, p + 4) Szexi (p, p + 6) Chen Sophie Germain (p, 2p + 1) Cunningham-lánc (p, 2p ± 1, …) Biztonságos (p, (p − 1)/2) Számtani sorozatban (p + a·n, n = 0, 1, …) Kiegyensúlyozott (egymást követő p − n, p, p + n)
Méret alapján	Titáni (1000+ számjegy) Gigantikus (10 000+) Mega (1 000 000+) Ismert legnagyobb
Komplex számok	Eisenstein-prím Gauss-prím
Összetett számok	Álprím Erős álprím Majdnem prím Félprím Interprím
Kapcsolódó fogalmak	Valószínű prím Ipari szintű prím Illegális prímszám Prímszámképlet Prímhézag
Az első 100 prím	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541
Prímszámok listája