Numărul Perrin

În teoria numerelor , numerele Perrin sunt membri ai unei secvențe liniare recurente :

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

și

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

Secvența numerelor Perrin începe cu

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

Istorie

Această secvență a fost menționată de Édouard Lucas în 1876. În 1899, Perrin a folosit în mod explicit aceeași secvență. Cel mai aprofundat studiu al acestei secvențe a fost făcut de Adams și Shanks (1982).

Proprietăți

Funcție de generare

Funcția generatoare a numerelor Perrin este

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

Reprezentare matrice

{\begin{pmatrix}0&1&0\\0&0&1\\1&1&0\end{pmatrix}}^{n}{\begin{pmatrix}3\\0\\2\end{pmatrix}}={\begin{ pmatrix}P\stânga(n\dreapta)\\P\left(n+1\dreapta)\\P\left(n+2\right)\end{pmatrix}}

Un analog al formulei lui Binet

Secvența numerelor Perrin poate fi scrisă în funcție de gradul rădăcinilor ecuației caracteristice

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

Această ecuație are trei rădăcini. Una dintre aceste rădăcini p este reală (cunoscută ca număr plastic ). Folosind-o și două rădăcini complexe conjugate q și r , se poate exprima numărul Perrin într-un mod similar cu formula lui Binet pentru numerele Lucas :

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

Deoarece valorile absolute ale rădăcinilor complexe q și r sunt mai mici decât 1, puterile acestor rădăcini vor tinde spre 0 pe măsură ce n crește . Pentru n mare , formula se simplifică la

P\stanga(n\dreapta)\aprox {p^{n))

Această formulă poate fi utilizată pentru a calcula rapid numerele Perrin pentru n mare . Raportul membrilor succesivi ai secvenței Perrin tinde spre p ≈ 1,324718. Această constantă joacă același rol pentru secvența Perrin ca și raportul de aur pentru numerele Lucas . O relație similară există între p și șirul Padovan , între raportul de aur și numerele Fibonacci și între raportul de argint și numerele Pell .

Formula de multiplicare

Din formulele lui Binet, putem obține formule pentru G ( kn ) în termeni de G ( n −1), G ( n ) și G ( n +1). Noi stim aia

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

Ceea ce ne oferă un sistem de trei ecuații liniare cu coeficienți din câmpul de expansiune al polinomului . Calculând matricea inversă, putem rezolva ecuațiile și obținem . Apoi putem ridica toate cele trei valori obținute la puterea k și calcula suma. $x^{3}-x-1$ $p^{n},q^{n},r^{n)$

Un exemplu de program în sistemul Magma :

P<x> := PolynomialRing(Rationals()); S<t> := SplittingField(x^3-x-1); P2<y> := PolynomialRing(S); p,q,r := Explode([r[1] : r în Roots(y^3-y-1)]); Mi:=Matrice([[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 în [-1..1]] ;

Lasă . Ca urmare a rezolvării sistemului, obținem $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\dreapta)\\23G(3n+1)&=& \left(v^{3}-w^{3}+6uv^{2}+9uw^{2}+6vw^{2}+9vu^{2}-3wu^{2}+6wv^{2} -6uvw\right)\end{matrice}}

Numărul 23 apare în aceste formule ca discriminant al polinomului care definește șirul ( ). $x^{3}-x-1$

Acest lucru permite calcularea celui de-al n-lea număr Perrin în aritmetica întregului folosind înmulțiri. $O(\log n)$

Primul și divizibilitatea

Pseudoprime numere Perrin

S-a dovedit că toate numerele prime p împart P ( p ). Reversul, însă, nu este adevărat - unele numere compuse n pot împărți P ( n ), astfel de numere sunt numite numere Perrin pseudo-prime .

Existența pseudoprimelor Perrin a fost considerată de Perrin însuși, dar nu s-a știut dacă au existat sau nu până când Adams și Shanks (1982) l-au descoperit pe cel mai mic dintre ele, 271441 = 521 2 . Următorul a fost . Sunt cunoscute șaptesprezece numere Perrin pseudo-prime, mai puțin de un miliard; [1] Jon Grantham a demonstrat [2] că există o infinitate de pseudoprime Perrin. $904631=7\times 13\times 9941$

Primele Perrin

Numerele Perrin, care sunt prime , formează șirul:

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

Weisstein a găsit un prim probabil Perrin P (263226) cu 32147 de cifre în mai 2006 [3] .

Note

↑ Secvența OEIS A013998 _
↑ John Grantham. Există infinit de multe pseudoprime Perrin // Journal of Number Theory : journal. - 2010. - Vol. 130 , nr. 5 . - P. 1117-1128 . - doi : 10.1016/j.jnt.2009.11.008 .
^ Weisstein , Eric W. Perrin Sequence pe site- ul Wolfram MathWorld .

Literatură

Adams, William; Shanks, Daniel. Teste de primalitate puternice care nu sunt suficiente // Matematica calculului : jurnal. - Societatea Americană de Matematică, 1982. - Vol. 39 , nr. 159 . - P. 255-300 . - doi : 10.2307/2007637 . — .

Furedi, Z.Numărul de mulțimi maxim independente din graficele conectate // Journal of Graph Theory : jurnal. - 1987. - Vol. 11 , nr. 4 . - P. 463-470 . - doi : 10.1002/jgt.3190110403 .

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

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