Numer Perrina

W matematyce liczby Perrina są definiowane przez relację powtarzalności

P. ( n ) = P. ( n - 2) + P. ( n - 3) dla n > 2 ,

z wartościami początkowymi

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

Sekwencja liczb Perrina zaczyna się od

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

Liczba różnych maksymalnych niezależnych zbiorów w grafie cykli n -wierzchołków jest liczona przez n -tą liczbę Perrina dla n > 1 .

Historia

Ta sekwencja została pośrednio wspomniana przez Édouarda Lucasa (1876). W 1899 roku o tej samej sekwencji wyraźnie wspomniał François Olivier Raoul Perrin. Najobszerniejsze omówienie tej sekwencji podali Adams i Shanks (1982).

Nieruchomości

Funkcja generująca

Funkcja generująca sekwencji Perrina to

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

Formuła macierzowa

${\ Displaystyle {\ rozpocząć {pmatrix} 0 i 1 i 0 \\ 0 i 0 i 1 \\ 1 i 1 i 0 \ koniec {pmatrix}} ^ {\! N} {\ rozpocząć {pmatrix} 3 \\ 0 \\ 2 \ koniec {pmatrix}} = {\ rozpocząć {pma trix}P\lewa(n\prawa)\\P\lewa(n+1\prawa)\\P\lewa(n+2\prawa)\end{pmacierz}}}$

Formuła podobna do Bineta

Spirala trójkątów równobocznych o długościach boków zgodnych z sekwencją Perrina.

Liczby Perrina można zapisać jako potęgi pierwiastków równania

${\ Displaystyle x ^ {3} -x-1 = 0.}$

To równanie ma 3 pierwiastki; jeden pierwiastek rzeczywisty p (znany jako liczba plastyczna ) i dwa pierwiastki sprzężone zespolone q i r . Biorąc pod uwagę te trzy pierwiastki, analogiem sekwencji Perrina wzoru Bineta jest sekwencja Lucasa

${\ Displaystyle P (n) = p ^ {n} + q ^ {n} + r ^ {n}.}$

Ponieważ wartości bezwzględne pierwiastków zespolonych q i r są mniejsze niż 1, potęgi tych pierwiastków zbliżają się do 0 dla dużych n . Dla dużych n wzór redukuje się do

${\ Displaystyle P (n) \ w przybliżeniu p ^ {n}}$

Formuły tej można użyć do szybkiego obliczenia wartości sekwencji Perrina dla dużych n . Stosunek kolejnych wyrazów w sekwencji Perrina zbliża się do p , czyli liczby plastycznej , która ma wartość około 1,324718. Ta stała ma taki sam związek z ciągiem Perrina, jak złoty podział z ciągiem Lucasa . Podobne powiązania istnieją również między p a ciągiem Padovana , między złotym podziałem a liczbami Fibonacciego oraz między srebrnym podziałem i liczby Pella .

Formuła mnożenia

Ze wzoru Bineta możemy otrzymać wzór na G ( kn ) pod względem G ( n - 1), G ( n ) i G ( n + 1); wiemy

${\ Displaystyle {\ rozpocząć {macierz} 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) i = i pp ^ {n} + & qq ^ {n} + & rr ^ {n} \ koniec {macierz}}}$

co daje nam trzy równania liniowe ze współczynnikami w polu podziału ${\ Displaystyle x ^ {3} -x-1}$ ; odwracając macierz , możemy rozwiązać dla $a$ je k - i

Przykładowy kod magmy :

P := Pierścień Wielomianu(Wymierne()); S := Dzielenie pola(x^3-x-1); P2 :=Pierścień wielomianowy(S); p,q,r := Explode([r[1] : r in Roots(y^3-y-1)]); Mi:=Macierz([[1/p,1/q,1/r],[1,1,1],[p,q,r]])^(-1); T :=Pierścień Wielomianu(S,3); v1 := ZmieńPierścień(Mi,T) *Macierz([[u],[v],[w]]); [p^i*v1[1,1]^3 + q^i*v1[2,1]^3 + r^i*v1[3,1]^3 : i w [-1..1]];

w rezultacie, jeśli mamy ${\ Displaystyle u = G (n-1), v = G (n), w = G (n + 1)}$ to

${\ Displaystyle {\ rozpocząć {macierz} 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(3 u^{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}+9v u^{2}-3wu^{2}+6wv^{2}-6uvw\right)\end{macierz}}}$

Liczba 23 wynika tutaj z wyróżnika definiującego wielomianu ciągu.

Pozwala to na obliczenie n -tej liczby Perrina przy użyciu arytmetyki liczb całkowitych w mnożeniach ${\ Displaystyle O (\ log n)}$ .

Liczby pierwsze i podzielność

Pseudopierwsze Perrina

Udowodniono , że dla wszystkich liczb pierwszych p , p dzieli P ( p ). Jednak sytuacja odwrotna nie jest prawdziwa: dla niektórych liczb złożonych n , n może nadal dzielić P ( n ). Jeśli n ma tę właściwość, nazywa się to „ liczbą pseudopierwszą Perrina ”.

Kilka pierwszych liczb pseudopierwszych Perrina to

271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431, ... (sekwencja A013998 w OEIS )

Kwestię istnienia liczb pseudopierwszych Perrina rozważał sam Perrin, ale nie było wiadomo, czy one istnieją, dopóki Adams i Shanks (1982) nie odkryli najmniejszej, 271441 = 521 ² ; następny najmniejszy to 904631 = 7 × 13 × 9941. Jest ich siedemnaście mniej niż miliard; Jon Grantham udowodnił, że istnieje nieskończenie wiele liczb pseudopierwszych Perrina.

Adams i Shanks (1982) zauważyli, że liczby pierwsze również spełniają warunek, że P (− p ) = −1 mod p . Kompozyty, w których zachowują się obie właściwości, nazywane są „ograniczonymi liczbami pseudopierwszymi Perrina” (sekwencja A018187 w OEIS ). Dalsze warunki można zastosować przy użyciu sześcioelementowej sygnatury n , która musi być jedną z trzech form (np. OEIS : A275612 i OEIS : A275613 ).

Chociaż liczby pseudopierwsze Perrina są rzadkie, w znacznym stopniu pokrywają się z liczbami pseudopierwszymi Fermata . Kontrastuje to z liczbami pseudopierwszymi Lucasa , które są antyskorelowane. Ten ostatni warunek jest wykorzystywany do uzyskania popularnego, wydajnego i bardziej efektywnego testu BPSW , który nie ma znanych liczb pseudopierwszych, a wiadomo, że najmniejsza jest większa niż 2 ⁶⁴ .

Liczby pierwsze Perrina

Liczba pierwsza Perrina to liczba Perrina, która jest liczbą pierwszą . Kilka pierwszych liczb pierwszych Perrina to:

2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071 579864797, ... (sekwencja A074788 w OEIS )

Dla tych liczb pierwszych Perrina indeks n z P ( n ) wynosi

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, ... (sekwencja A112881 w OEIS )

Generowanie P ( n ), gdzie n jest ujemną liczbą całkowitą, daje podobną właściwość dotyczącą pierwszości: jeśli n jest liczbą ujemną, to P ( n ) jest liczbą pierwszą, gdy P ( n ) mod − n = − n − 1. Następująca sekwencja reprezentuje P ( n ) dla wszystkich n , które są ujemnymi liczbami całkowitymi:

-1, 1, 2, -3, 4, -2, -1, 5, -7, 6, -1, -6, 12, -13, 7, 5, -18, 25, -20, 2, 23, -43, 45, -22, -21, 66, -88, 67, -1, ... (sekwencja A078712 w OEIS )

Notatki

• Furedi, Zoltán (1987). „Liczba maksymalnych niezależnych zestawów w połączonych grafach”. Dziennik teorii grafów . 11 (4): 463–470. doi : 10.1002/jgt.3190110403 .

•   Knuth, Donald E. (2011). Sztuka programowania komputerowego , tom 4A: Algorytmy kombinatoryczne, część 1 . Addison-Wesley. ISBN 978-0201038040 .

• Grantham, Jon (2010). „Istnieje nieskończenie wiele liczb pseudopierwszych Perrina” (PDF) . Dziennik teorii liczb   . 130 (5): 1117–1128. ar Xiv : 1903.06825 . doi : 10.1016/j.jnt.2009.11.008 . S2CID 13935283 .

Dalsza lektura

•    Adams, William; Shanks, Daniel (1982). „Silne testy pierwszości, które nie są wystarczające” . Matematyka obliczeń . Amerykańskie Towarzystwo Matematyczne. 39 (159): 255–300. doi : 10.2307/2007637 . JSTOR 2007637 . MR 0658231 .

• Perrin, R. (1899). „Zapytanie 1484”. L'Intermédiaire des Mathématiciens . 6 : 76.

• Lucas, E. (1878). „Théorie des fonctions numériques simplement périodiques”.   American Journal of Mathematics . Wydawnictwo Uniwersytetu Johnsa Hopkinsa. 1 (3): 197–240. doi : 10.2307/2369311 . JSTOR 2369311 .

Linki zewnętrzne

• Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence
• „Lucas pseudopierwsze” . MathPages.com .
• „Sekwencja Perrina” . MathPages.com .
• OEIS A225876 (kompozyt n, który dzieli s (n) + 1, gdzie s to ...) - Sekwencja podobna do Perrina
• Testy pierwszości Perrina