Don't take life too seriously: it's just a temporary situation

Perrin (numeri di)

Sequenze  Teoria dei grafi 

I numeri di Perrin sono i numeri interi appartenenti alla sequenza di Perrin, definita come: P0 = 3, P1 = 0, P2 = 2 e Pn = Pn – 2 + Pn – 3. Sebbene esaminata prima da Lucas, prende il nome da François Olivier Raoul Perrin, che dimostrò che se p è primo, divide Pp (v. pseudoprimi di Perrin). La ricorrenza è uguale a quella che definisce i numeri di Padovan, ma i termini iniziali sono differenti.

 

Per n > 2, Pn è il numero di insiemi massimali indipendenti in un grafo ciclico di ordine n. In altri termini, dato un grafo formato da un anello di n punti, ciascuno connesso solo al precedente e al successivo, si possono scegliere Pn insiemi differenti di punti non connessi tra loro, in modo che ogni punto del grafo appartenga all'insieme o sia connesso a un punto appartenente all'insieme.

La figura seguente mostra i 5 possibili insiemi (in blu) in un grafo ciclico con 6 punti.

Raffigurazione dei i 5 insiemi massimali indipendenti in un grafo ciclico con 6 punti

 

La definizione può essere estesa a indici negativi: Pn = Pn + 3Pn + 1.

 

Il rapporto tra numeri di Perrin consecutivi con indici positivi tende alla costante plastica.

 

Per n tendente a infinito Pn tende a Pn, dove P è la costante plastica.

 

Alcune formule, che permettono di calcolare i numeri di Perrin:

Formula per il calcolo dei numeri di Perrin, dove r1, r2 e r3 sono le soluzioni dell’equazione x3x – 1 = 0, circa uguali a 1.3247179572 (costante plastica) e –0.6623589786 ± 0.5622795121i;

Formula per il calcolo dei numeri di Perrin, dove P è la costante plastica.

 

Alcune formule permettono di calcolare un numero di Perrin senza dover calcolare tutti i precedenti:

Formula per il calcolo dei numeri di Perrin;

P2n + 1 = PnPn + 1 + P1 – n;

Pmn + k = PmPm(n – 1) + kPmPm(n – 2) + k + Pm(n – 3) + k;

Formula per il calcolo dei numeri di Perrin;

Formula per il calcolo dei numeri di Perrin;

Formula per il calcolo dei numeri di Perrin;

Formula per il calcolo dei numeri di Perrin;

Formula per il calcolo dei numeri di Perrin;

Formula per il calcolo dei numeri di Perrin;

Formula per il calcolo dei numeri di Perrin;

Formula per il calcolo dei numeri di Perrin, dove a(r) = r mod 2, b(r) = –r mod 3 e r uguale a 0, 2, 3, 4 o 5.

 

Come nel caso dei numeri di Fibonacci e Padovan, anche i numeri di Perrin possono essere ricavati dalle potenze di una matrice: se Matrice Q, allora Formula per il calcolo di numeri di Perrin tramite potenze della matrice Q. Per esempio, Esempio di calcolo di numeri di Perrin tramite potenze della matrice Q.

 

Alcune formule per calcolare somme di numeri di Perrin:

Formula per il calcolo di somme di numeri di Perrin;

Formula per il calcolo di somme di numeri di Perrin;

Formula per il calcolo di somme di numeri di Perrin.

 

La funzione generatrice è: Funzione generatrice dei numeri di Perrin.

 

La tabella seguente riporta i numeri di Perrin fino a P20.

n

Pn

0

3

1

0

2

2

3

3

4

2

5

5

6

5

7

7

8

10

9

12

10

17

11

22

12

29

13

39

14

51

15

68

16

90

17

119

18

158

19

209

20

277

 

Se p è primo, PnpPn mod p, ma la stessa proprietà vale per alcuni (rari) valori composti di p, detti “pseudoprimi di Perrin”.

 

Tra i numeri di Perrin vi sono alcuni primi, detti “primi di Perrin”; i pochi noti corrispondono agli indici: 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, 16260, 18926, 23698, 40059, 45003, 73807, 91405* (Eric W. Weisstein, 2005), 263226* (Eric W. Weisstein, 2006), 316872* (Eric W. Weisstein, 2007), 321874* (Eric W. Weisstein, 2007), 324098* (Eric W. Weisstein, 2009), 581132* (Eric W. Weisstein, 20011) (l'asterisco indica i primi probabili). I primi corrispondenti sono: 2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797, 22584751787583336797527561822649328254745329.

 

L’unico quadrato noto tra i numeri di Perrin è 0; se ve ne sono altri, hanno indice superiore al milione. Ritengo probabile che, come nelle sequenze di Fibonacci e Lucas, siano in numero finito, ma che io sappia non è stato dimostrato.

Tabelle numeriche

I numeri di Perrin fino a P1000.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.