Numărul Perrin

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

În matematică , numerele Perrin sunt definite de relația de recurență

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

Și

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

Secvența numerică a lui Perrin începe cu

3 , 0 , 2 , 3, 2, 5 , 5, 7 , 10 , 12 , 17 , 22 , 29 , 39 ... [1]

Numărul diferitelor maxime seturi independente într - un grafic ciclu cu n vârfuri este numărat de numărul nth Perrin pentru n> 1. [2]

Istorie

Această secvență fusese deja menționată implicit de Édouard Lucas (1876). În 1899, aceeași secvență a fost menționată în mod explicit de François Olivier Raoul Perrin. [3] Cel mai extins tratament al acestei secvențe a fost realizat de Adams și Shanks (1982).

Proprietate

Funcție generatoare

Funcția generatoare a secvenței Perrin este

Formula matricei

Formula similară a lui Binet

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

Această ecuație are 3 rădăcini; o rădăcină reală p (cunoscută sub numele de plastic ) și două rădăcini complexe conjugate q și r . Având în vedere aceste trei rădăcini, analogul pentru secvența Perrin a formulei Binet pentru secvența Lucas este

Deoarece mărimile rădăcinilor complexe q și r sunt ambele mai mici de 1, puterile acestor rădăcini se apropie de 0 pentru n mare. Pentru n mare formula se reduce la

Această formulă poate fi utilizată pentru a calcula rapid valorile secvenței Perrin pentru n mare. Raportul dintre termenii succesivi din secvența Perrin se apropie de p , care este numărul plastic , care are o valoare de aproximativ 1,324718. Această constantă are aceeași relație cu secvența Perrin ca și raportul auriu cu secvența Lucas . Legături similare există și între p și secvența Padovan , între secțiunea aurie și secvența Fibonacci și între secțiunea argintie și numerele Pell .

Formula de multiplicare

Din formula lui Binet, putem obține o formulă pentru G ( kn ) în termeni de G ( n −1), G ( n ) și G ( n +1); noi stim

ceea ce ne oferă trei ecuații liniare cu coeficienții pe câmpul de divizare a ; inversând o matrice pentru care putem rezolva și apoi le putem ridica la k-th și putem calcula suma.

Exemplu de cod 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: = 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 în [-1..1]] ;

cu rezultatul că, dacă avem , asa de

Numărul 23 apare aici din discriminantul secvenței care definește polinomul.

Acest lucru ne permite să calculăm numărul Perrin cu ajutorul aritmeticii întregi din multipli.

Prim și divizibilitate

Pseudoprime din Perrin

S-a arătat că pentru toate numerele prime p , p împarte P ( p ). Cu toate acestea, inversul nu este adevărat: pentru unele numere compuse n , n poate împărți P ( n ). Dacă n are această proprietate, se numește pseudoprima lui Perrin .

Problema existenței pseudoprimelor lui Perrin a fost luată în considerare de Perrin însuși, dar nu se știa dacă acestea există până când Adams și Shanks (1982) au descoperit cel mai mic, 271441 = 521 2 ; următorul mai mic este 904631 = 7 x 13 x 9941. Există șaptesprezece mai puțin de un miliard; [4] Jon Grantham a demonstrat [5] că există infinite pseudoprime Perrin.

În primul rând Perrin

Un prim Perrin este un număr Perrin care este un număr prim . Primele inițiale ale lui Perrin sunt:

2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797 [6]

EW Weisstein a găsit un prim Perrin probabil de 32.147 cifre, P (263226), în mai 2006.

Notă

Bibliografie

  • Knuth, Donald E., The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1 , Addison-Wesley, 2011, ISBN 0-201-03804-8 .
  • Perrin, R., Interogarea 1484 , în L'Intermédiaire des Mathématiciens , vol. 6, 1899, p. 76.

linkuri externe

Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă cu matematica