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:
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
[szerkesztés]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
[szerkesztés]Generátorfüggvény
[szerkesztés]A Perrin-sorozat generátorfüggvénye:
Mátrixformula
[szerkesztés]Binet-féle formula
[szerkesztés]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
[szerkesztés]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
[szerkesztés]Perrin-álprímek
[szerkesztés]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 = 5212 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 264-nél.
Perrin-prímek
[szerkesztés]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
[szerkesztés]- ↑ (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
[szerkeszté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.