Numero di Perrin

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

In matematica, i numeri di Perrin sono definiti dalla relazione di ricorrenza

,

e

per .

La sequenza dei numeri di Perrin inizia con

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

Il numero dei diversi insiemi indipendenti massimali in un grafo ciclo con vertici è conteggiato dal numero Perrin -esimo per .[2]

Storia[modifica | modifica wikitesto]

Questa sequenza era già stata menzionata implicitamente da Édouard Lucas (1876). Nel 1899, la stessa sequenza fu menzionata esplicitamente da François Olivier Raoul Perrin.[3] La trattazione più estesa di questa sequenza fu fatta da Adams e Shanks (1982).

Proprietà[modifica | modifica wikitesto]

Funzione generatrice[modifica | modifica wikitesto]

La funzione generatrice della sequenza di Perrin è

Formula della matrice[modifica | modifica wikitesto]

Formula simile di Binet[modifica | modifica wikitesto]

La sequenza dei numeri di Perrin può essere scritta in termini di potenze delle radici dell'equazione

Questa equazione ha 3 radici; una radice reale (nota come il numero plastico) e due radici complesse coniugate ed . Date queste tre radici, l'analogo per la sequenza di Perrin della formula di Binet per la sequenza di Lucas è

Poiché le grandezze delle radici complesse ed sono entrambe minori di , le potenze di queste radici si avvicinano a per grande. Per grande la formula si riduce a:

Questa formula può essere usata per calcolare rapidamente i valori della sequenza di Perrin per grande. Il rapporto di termini successivi nella sequenza di Perrin si avvicina a , ossia al numero plastico, che ha un valore approssimativamente di 1,324718. Questa costante ha con la sequenza di Perrin la stessa relazione che la sezione aurea ha con la sequenza di Lucas. Collegamenti simili esistono anche tra e la sequenza di Padovan, tra la sezione aurea e la successione di Fibonacci, e tra la sezione argentea e i numeri di Pell.

Formula della moltiplicazione[modifica | modifica wikitesto]

Dalla formula di Binet, possiamo ottenere una formula per in termini di e ; sappiamo che:

che ci dà tre equazioni lineari con i coefficienti sul campo di spezzamento di ; invertendo una matrice possiamo risolvere per e poi possiamo elevarle alla -esima e computare la somma.

Esempio in codice magma:

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

con il risultato che, se abbiamo , allora

Il numero 23 qui sorge dalla discriminante del polinomio definitore della sequenza.

Questo permette di computare il numero di Perrin -esimo usando l'aritmetica degli interi in multipli.

Primi e divisibilità[modifica | modifica wikitesto]

Pseudoprimi di Perrin[modifica | modifica wikitesto]

È stato dimostrato che per tutti i numeri primi , divide . Tuttavia, l'inverso non è vero: per alcuni numeri composti , può dividere . Se ha questa proprietà, è chiamato pseudoprimo di Perrin.

La questione dell'esistenza degli pseudoprimi di Perrin fu considerata dallo stesso Perrin, ma non si sapeva se esistessero finché Adams e Shanks (1982) non scoprirono il più piccolo, 271441 = 5212; il successivo più piccolo è 904631 = 7 x 13 x 9941. Ce ne sono diciassette minori di un miliardo;[4] Jon Grantham ha dimostrato[5] che ci sono infiniti pseudoprimi di Perrin.

Primi di Perrin[modifica | modifica wikitesto]

Un primo di Perrin è un numero di Perrin che è un numero primo. I primi iniziali di Perrin sono:

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

Eric W. Weisstein trovò un probabile primo di Perrin a 32.147 cifre, P(263226), nel maggio 2006.

Note[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]

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

Collegamenti esterni[modifica | modifica wikitesto]

  Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica