Perrin szám

A számelméletben a Perrin-számok egy lineáris ismétlődő sorozat tagjai :

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

és

P ( n ) = P ( n − 2) + P ( n − 3), n > 2 esetén.

A Perrin-számok sorozata ezzel kezdődik

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

Történelem

Ezt a sorozatot Édouard Lucas említette 1876-ban. 1899-ben Perrin kifejezetten ugyanazt a sorozatot használta. Ennek a sorozatnak a legmélyebb vizsgálatát Adams és Shanks (1982) végezte.

Tulajdonságok

Függvény generálása

A Perrin-számok generáló függvénye az

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

Mátrix ábrázolás

{\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 képletének analógja

A Perrin-számok sorozata felírható a karakterisztikus egyenlet gyökeinek mértékével

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

Ennek az egyenletnek három gyöke van. Az egyik p gyök valódi ( plasztikus számként ismert ). Ennek és két konjugált q és r komplex gyöknek a használatával a Perrin-számot Binet Lucas-számokra vonatkozó képletéhez hasonló módon fejezhetjük ki :

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

Mivel a q és r komplex gyökök abszolút értéke kisebb, mint 1, ezeknek a gyökeknek a hatványai 0-ra hajlanak, ahogy n növekszik . Nagy n esetén a képlet leegyszerűsödik

P\left(n\right)\approx {p^{n))

Ezzel a képlettel gyorsan kiszámítható a Perrin-szám nagy n esetén . A Perrin szekvencia egymást követő tagjainak aránya p ≈ 1,324718. Ez a konstans ugyanazt a szerepet játszik a Perrin-sorozatban, mint az aranymetszés a Lucas-számoknál . Hasonló kapcsolat van p és a Padovan sorozat között, az aranymetszés és a Fibonacci-számok, valamint az ezüstmetszés és a Pell-számok között .

Szorzási képlet

Binet képleteiből G ( kn ) képleteket kaphatunk G ( n −1 ), G ( n ) és G ( n +1 ) függvényében. Tudjuk

{\begin{mátrix}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{mátrix}}

Ez egy három lineáris egyenletrendszert ad a polinom kiterjesztési mezőjének együtthatóival . Az inverz mátrix kiszámításával meg tudjuk oldani az egyenleteket, és megkapjuk . Ezután mindhárom kapott értéket felemelhetjük k hatványra , és kiszámíthatjuk az összeget. $x^{3}-x-1$ ${\displaystyle p^{n},q^{n},r^{n))$

Egy példaprogram a Magma rendszerben :

P<x> := Polinomgyûrû(Rationals()); S<t> := Felosztásmező(x^3-x-1); P2<y> := Polinomgyűrű(S); p,q,r := Explode([r[1] : r in Roots(y^3-y-1)]); Mi:=Mátrix([[1/p,1/q,1/r],[1,1,1],[p,q,r]])^(-1); T<u,v,w> := Polinomgyűrű(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]] ;

Hadd . A rendszer megoldásának eredményeként azt kapjuk ${\megjelenítési stílus u=G(n-1),v=G(n),w=G(n+1)}$

{\begin{mátrix}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{mátrix}}

A 23-as szám ezekben a képletekben a sorozatot ( ) meghatározó polinom diszkriminánsaként jelenik meg. $x^{3}-x-1$

Ez lehetővé teszi az n-edik Perrin-szám kiszámítását egész aritmetikában szorzások segítségével. $O(\log n)$

Prím és oszthatóság

Pszeudoprime Perrin számok

Bebizonyosodott, hogy minden p prím osztja P ( p ). Ennek a fordítottja azonban nem igaz - egyes n összetett számok oszthatják P ( n ), az ilyen számokat pszeudo-prím Perrin -számoknak nevezzük .

A Perrin pszeudoprímek létezését maga Perrin is fontolóra vette, de nem lehetett tudni, hogy léteznek-e vagy sem, amíg Adams és Shanks (1982) fel nem fedezte a legkisebbet, 271441 = 521 2 . A következő volt . Tizenhét pszeudo-prím Perrin-szám ismert, kevesebb mint egymilliárd; [1] Jon Grantham bebizonyította [2] , hogy végtelenül sok Perrin pszeudoprím létezik. $904631=7\times 13\times 9941$

Perrin prímszámok

A Perrin-számok, amelyek prímszámok , a következő sorozatot alkotják:

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

Weisstein 2006 májusában talált egy valószínű Perrin - prímet ( 263226 ), amely 32147 számjegyből áll [3] .

Jegyzetek

↑ OEIS szekvencia A013998 _
↑ John Grantham. Végtelenül sok Perrin-pszeudoprím létezik // Journal of Number Theory : Journal. - 2010. - 20. évf. 130 , sz. 5 . - P. 1117-1128 . - doi : 10.1016/j.jnt.2009.11.008 .
↑ Weisstein, Eric W. Perrin Sequence a Wolfram MathWorld webhelyen .

Irodalom

Adams, William; Shanks, Daniel. Erős primalitási tesztek, amelyek nem elegendőek // Számítási matematika : folyóirat. - American Mathematical Society, 1982. - Vol. 39 , sz. 159 . - P. 255-300 . - doi : 10.2307/2007637 . — .

Furedi, Z.A maximálisan független halmazok száma összekapcsolt gráfokban // Journal of Graph Theory : folyóirat. - 1987. - 1. évf. 11 , sz. 4 . - P. 463-470 . - doi : 10.1002/jgt.3190110403 .

Lucas, E.Théorie des fonctions numériques simplement périodiques (francia) // American Journal of Mathematics : magazin. - The Johns Hopkins University Press, 1878. - Vol. 1 , n o 3 . - P. 197-240 . - doi : 10.2307/2369311 . — .

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