Numero di Perrin

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

${\displaystyle P(0)=3,\,P(1)=0,\,P(2)=2}$,

e

${\displaystyle P(n)=P(n-2)+P(n-3)}$ per ${\displaystyle n>2}$.

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 ${\displaystyle n}$ vertici è conteggiato dal numero Perrin ${\displaystyle n}$-esimo per ${\displaystyle n>1}$.^[2]

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).

La funzione generatrice della sequenza di Perrin è

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

${\displaystyle {\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}}}$

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

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

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

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

Poiché le grandezze delle radici complesse ${\displaystyle q}$ ed ${\displaystyle r}$ sono entrambe minori di ${\displaystyle 1}$, le potenze di queste radici si avvicinano a ${\displaystyle 0}$ per ${\displaystyle n}$ grande. Per ${\displaystyle n}$ grande la formula si riduce a:

${\displaystyle P\left(n\right)\approx {p^{n}}}$

Questa formula può essere usata per calcolare rapidamente i valori della sequenza di Perrin per ${\displaystyle n}$ grande. Il rapporto di termini successivi nella sequenza di Perrin si avvicina a ${\displaystyle p}$, 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 ${\displaystyle p}$ e la sequenza di Padovan, tra la sezione aurea e la successione di Fibonacci, e tra la sezione argentea e i numeri di Pell.

Dalla formula di Binet, possiamo ottenere una formula per ${\displaystyle G(kn)}$ in termini di ${\displaystyle G(n-1),\,G(n)}$ e ${\displaystyle G(n+1)}$; sappiamo che:

${\displaystyle {\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{matrix}}}$

che ci dà tre equazioni lineari con i coefficienti sul campo di spezzamento di ${\displaystyle x^{3}-x-1}$; invertendo una matrice possiamo risolvere per ${\displaystyle p^{n},q^{n},r^{n}}$ e poi possiamo elevarle alla ${\displaystyle k}$-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 ${\displaystyle u=G(n-1),v=G(n),w=G(n+1)}$, allora

${\displaystyle {\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\right)\\23G(3n+1)&=&\left(v^{3}-w^{3}+6uv^{2}+9uw^{2}+6vw^{2}+9vu^{2}-3wu^{2}+6wv^{2}-6uvw\right)\end{matrix}}}$

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

Questo permette di computare il numero di Perrin ${\displaystyle n}$-esimo usando l'aritmetica degli interi in ${\displaystyle O(\log n)}$ multipli.

È stato dimostrato che per tutti i numeri primi ${\displaystyle p}$, ${\displaystyle p}$ divide ${\displaystyle P(p)}$. Tuttavia, l'inverso non è vero: per alcuni numeri composti ${\displaystyle n}$, ${\displaystyle n}$ può dividere ${\displaystyle P(n)}$. Se ${\displaystyle n}$ 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 = 521²; 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.

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.

• (EN) Adams, William; Shanks, Daniel, Strong primality tests that are not sufficient, in Mathematics of Computation, vol. 39, n. 159, American Mathematical Society, 1982, pp. 255–300, DOI:10.2307/2007637, JSTOR 2007637, MR 0658231.

• (EN) Füredi, Zoltán, The number of maximal independent sets in connected graphs, in Journal of Graph Theory, vol. 11, n. 4, 1987, pp. 463–470, DOI:10.1002/jgt.3190110403.

• (EN) Knuth, Donald E., The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, ISBN 0-201-03804-8.

• (FR) Lucas, Édouard, Théorie des fonctions numériques simplement périodiques, in American Journal of Mathematics, vol. 1, n. 3, The Johns Hopkins University Press, 1878, pp. 197–240, DOI:10.2307/2369311, JSTOR 2369311.

• (FR) Perrin, R., Query 1484, in L'Intermédiaire des Mathématiciens, vol. 6, 1899, p. 76.

• (EN) Eric W. Weisstein, Numero di Perrin, su MathWorld, Wolfram Research.
• (DE) Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence, su ai.univie.ac.at. URL consultato il 23 marzo 2014 (archiviato dall'url originale l'8 novembre 2005).
• (EN) MathPages - Lucas Pseudoprimes, su mathpages.com.
• (EN) MathPages - Perrin's Sequence, su mathpages.com.
• (EN) Perrin-like sequence, su oeis.org.

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri

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