Perrin-számok

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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

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

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.

További információk[szerkesztés]