Perrinovo číslo

V teorii čísel jsou Perrinova čísla členy lineární opakující se sekvence :

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

P ( n ) = P ( n − 2) + P ( n − 3) pro n > 2.

Posloupnost Perrinových čísel začíná na

3 , 0 , 2 , 3, 2, 5 , 5, 7 , 10 , 12 , 17 , 22 , 29 , 39 , ... ( sekvence OEIS A001608 )

Historie

Tuto sekvenci zmínil Édouard Lucas v roce 1876 . V roce 1899 Perrin výslovně použil stejnou sekvenci. Nejpodrobnější studii této sekvence provedli Adams a Shanks (1982).

Vlastnosti

Generující funkce

Generující funkce Perrinových čísel je

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

Maticová reprezentace

{\begin{pmatrix}0&1&0\\0&0&1\\1&1&0\end{pmatrix}}^{n}{\begin{pmatrix}3\\0\\2\end{pmatrix}}={\begin{ pmatrix}P\levá(n\vpravo)\\P\vlevo (n+1\vpravo)\\P\vlevo (n+2\vpravo)\end{pmatrix}}

Analoga Binetova vzorce

Posloupnost Perrinových čísel lze zapsat z hlediska stupně kořenů charakteristické rovnice

x^{3}-x-1=0.

Tato rovnice má tři kořeny. Jeden z těchto kořenů p je skutečný (známý jako plastické číslo ). Pomocí něj a dvou konjugovaných komplexních kořenů q a r lze vyjádřit Perrinovo číslo podobným způsobem jako Binetův vzorec pro Lucasova čísla :

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

Protože absolutní hodnoty komplexních kořenů q a r jsou menší než 1, budou mocniny těchto kořenů mít tendenci k 0, jak n vzrůstá . Pro velké n se vzorec zjednoduší na

P\left(n\right)\přibližně {p^{n))

Tento vzorec lze použít k rychlému výpočtu Perrinových čísel pro velké n . Poměr po sobě jdoucích členů Perrinovy sekvence má tendenci k p ≈ 1,324718. Tato konstanta hraje pro Perrinovu sekvenci stejnou roli jako zlatý řez pro Lucasova čísla . Podobný vztah existuje mezi p a Padovanovou sekvencí , mezi zlatým řezem a Fibonacciho čísly a mezi stříbrným poměrem a Pellovými čísly .

Vzorec násobení

Z Binetových vzorců můžeme získat vzorce pro G ( kn ) ve smyslu G ( n −1), G ( n ) a G ( n +1). Víme, že

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

Což nám dává systém tří lineárních rovnic s koeficienty z expanzního pole polynomu . Výpočtem inverzní matice můžeme vyřešit rovnice a získat . Poté můžeme všechny tři získané hodnoty zvýšit na mocninu k a vypočítat součet. $x^{3}-x-1$ ${\displaystyle p^{n},q^{n},r^{n))$

Příklad programu v systému Magma :

P<x> := PolynomialRing(Rationals()); S<t> := SplittingField(x^3-x-1); P2<y> := PolynomialRing(S); p,q,r := Explode([r[1] : r v kořenech(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 v [-1..1]] ;

Nechte _ V důsledku řešení systému získáme $u=G(n-1),v=G(n),w=G(n+1)$

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

Číslo 23 se v těchto vzorcích objevuje jako diskriminant polynomu, který definuje posloupnost ( ). $x^{3}-x-1$

To umožňuje vypočítat n-té Perrinovo číslo v celočíselné aritmetice pomocí násobení. $O(\log n)$

Prvočíslo a dělitelnost

Pseudoprimární Perrinova čísla

Je dokázáno, že všechna prvočísla p dělí P ( p ). Opak však neplatí - některá složená čísla n mohou dělit P ( n ), taková čísla se nazývají pseudoprvočísla Perrinova .

O existenci Perrinových pseudoprimes uvažoval sám Perrin, ale nebylo známo, zda existují či nikoli, dokud Adams a Shanks (1982) neobjevili nejmenší z nich, 271441 = 521 2 . Další byl . Je známo sedmnáct pseudoprvních Perrinových čísel, méně než miliarda; [1] Jon Grantham dokázal [2] , že existuje nekonečně mnoho Perrinových pseudoprimes. $904631=7\times 13\times 9941$

Perrin připraví

Perrinova čísla, která jsou prvočísla , tvoří posloupnost:

2 3 5 7 17 29 277 367 853 14197 43721 1442968193 792606555396977 187278659180417234321 668279478041

Weisstein našel pravděpodobné Perrinovo prvočíslo P (263226) s 32147 číslicemi v květnu 2006 [3] .

Poznámky

↑ OEIS sekvence A013998 _
↑ John Grantham. Existuje nekonečně mnoho Perrinových pseudoprimes // Journal of Number Theory : journal. - 2010. - Sv. 130 , č. 5 . - S. 1117-1128 . - doi : 10.1016/j.jnt.2009.11.008 .
↑ Weisstein, Eric W. Perrin Sequence na webu Wolfram MathWorld .

Literatura

Adams, William; Shanksi, Danieli. Silné testy primality, které nejsou dostatečné // Matematika počítání : deník. - Americká matematická společnost, 1982. - Sv. 39 , č. 159 . - S. 255-300 . - doi : 10.2307/2007637 . — .

Furedi, Z.Počet maximálně nezávislých množin v spojených grafech // Journal of Graph Theory : deník. - 1987. - Sv. 11 , č. 4 . - S. 463-470 . - doi : 10.1002/jgt.3190110403 .

Lucas, E.Théorie des fonctions numériques simplement périodiques (francouzsky) // American Journal of Mathematics : magazine. - The Johns Hopkins University Press, 1878. - Sv. 1 , č . 3 . - str. 197-240 . - doi : 10.2307/2369311 . — .

Perrin, R. Query 1484 (neopr.) // L'Intermediaaire Des Mathematiciens. - 1899. - T. 6 . - S. 76 .