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

Pisano (numeri di)

Sequenze  Teoria dei numeri 

Per qualsiasi sequenza di interi nella quale il numero successivo sia ottenuto sommando alcuni dei precedenti, moltiplicati per coefficienti interi, anche negativi, S. Täklind dimostrò nel 1944 che i resti modulo un qualsiasi intero n sono periodici. In particolare questo vale per i numeri di Fibonacci generalizzati, inclusi i numeri di Fibonacci e di Lucas, per i quali il periodo non è maggiore di n2 – 1.

 

Si chiamano “numeri di Pisano” o “periodi di Pisano”, in onore di Leonardo Pisano, più noto come Fibonacci, le lunghezze P(n) dei periodi dei numeri di Fibonacci.

 

Alcuni valori dei numeri di Pisano:

  • P(2n) = 3 • 2n – 1 (Kramer e Hoggatt, 1972);

  • P(3n) = 8 • 3n – 1;

  • P(5n) = 4 • 5n;

  • P(10) = 60, ossia l’ultima cifra si ripete con periodo 60 (Lagrange, 1774);

  • P(100) = 300, ossia le ultime 2 cifre si ripetono con periodo 300 (S. Geller, 1963);

  • per n > 2, P(10n) = 15 • 10n – 1, ossia le ultime n cifre si ripetono con quel periodo (S. Geller, 1963);

  • P(n2) = P(n) se e solo se n è 6 o 12;

  • se p è primo, P(p2) = pP(p);

  • P(F2n) = 4n;

  • P(F2n + 1) = 8n + 4;

  • P(L2n + 1) = 4n + 2.

 

Alcune proprietà dei numeri di Pisano:

  • P(n) è pari per n > 2 (Donald Dines Wall, 1960);

  • P(n) = n se e solo se n = 24 • 5k, con k > 0 (J.D. Fulton e W.L. Morris, 1969);

  • P(n) ≤ 6n; in particolare P(n) = 6n se e solo se n = 2 • 5k, P(n) = 4n se e solo se n = 5k; per gli altri interi P(n) < 4n;

  • P(n) = n2 – 1 solo per n uguale a 2 o 3;

  • se Scomposizione di n in fattori primi è la scomposizione di n in fattori primi, Formula per il calcolo di P(n) (Donald Dines Wall, 1960), pertanto se n e m non hanno divisori comuni, il P(mn) = mcm(P(m), P(n));

  • se P(n) = k, Fk è multiplo di n;

  • se n divide m, P(n) divide P(m);

  • se p è un primo dispari della forma 5n ± 1, P(p) divide p – 1 (Donald Dines Wall, 1960); inoltre se p ha una radice primitiva di Fibonacci, P(p) = p – 1;

  • se p è un primo dispari della forma 5n ± 2, P(p) divide p2 – 1 e 2p + 2 ed è multiplo di 4 (Donald Dines Wall, 1960

  • se p è primo e P(p) = P(ps) ≠ P(ps + 1), allora P(pt) = ptsP(p) per ts (Donald Dines Wall, 1960)

  • per n > 2, se m è il minimo intero tale che è pari e n divide Fm oppure è dispari e n divide Fm – 1 + Fm + 1, allora P(n) = 2m;

  • Somma dei numeri di Fibonacci su un intero periodo dei resti è divisibile per n.

 

La tabella seguente mostra i numeri di Pisano P(n) per n fino a 20.

n

P(n)

1

1

2

3

3

8

4

6

5

20

6

24

7

16

8

12

9

24

10

60

11

10

12

24

13

28

14

48

15

40

16

24

17

36

18

24

19

18

20

60

 

Il calcolo di P(n) si riconduce al calcolo di P(pn), per p primo, ma non si conosce alcuna formula diretta per calcolare P(pn), con p primo. Per le potenze di un primo p, P(pn) = P(p) per n < m, P(pn) = pnmP(p) altrimenti, dove m dipende da p (D.D. Wall, 1960); m è 1 se e solo se p non è un primo di Wall – Sun – Sun; non si conosce alcun primo di questo tipo e potrebbero non essercene.

 

Se k è il minimo intero tale che Fk sia multiplo di n, P(n) = km, dove m è il minimo intero maggiore di zero tale che F(k + 1)^ m ≡ 1 mod n. Per esempio, per n = 10, k = 15 perché F15 = 610 e nessun numero di Fibonacci inferiore e maggiore di 0 è multiplo di 10; m = 4, perché F16 = 987, 9874 ≡ 1 mod 10 e 4 è il minimo intero maggiore di 0 con questa proprietà, quindi P(10) = 15 • 4 = 60.

Nella formula m può essere solo 1, 2 o 4; se p è un primo dispari e n divide Fp, P(p) = 4k.

Se n è primo e k = 2p con p primo dispari, P(n) = 4p.

Se n è primo e k = 4p con p primo dispari, P(n) = 8p.

Se p e q sono primi e p è dispari, P(q) = 4p se e solo se q divide Fp.

 

I resti ottenuti dividendo i numeri di Fibonacci per n contengono tutti i valori da 0 a n – 1 (ossia formano un sistema completo di resti) se e solo se n ha la forma m • 5k, dove m è 1, 2, 4, 6, 7, 14 o 3r, quindi in particolare gli unici primi modulo i quali si abbia un sistema completo di resti sono: 2, 3, 5 e 7.

 

Solo i resti modulo potenze di 5 sono uniformemente distribuiti, ossia tutti i resti possibili compaiono lo stesso numero di volte nel periodo.

 

Una sorprendente occorrenza dei numeri di Pisano si ha in una procedura di riordino di una matrice.

Data una matrice quadrata, se ne costruisce un’altra prendendo come prima riga la diagonale maggiore, come seconda la diagonale immediatamente superiore, come terza quella ancora superiore e così via. Le diagonali diverse dalla principale vanno considerate spezzate in due parti: quando seguendole si raggiunge l’ultima colonna della matrice, si continua dall’elemento sulla prima colonna della riga seguente.

Per esempio, partendo dalla matrice Matrice 4 × 4 si ottiene la matrice Matrice 4 × 4 dopo il riordino degli elementi.

Dato che ripetendo la procedura si può ottenere solo un numero finito di matrici diverse, non sorprende che dopo un certo numero di ripetizioni si ottenga di nuovo la matrice di partenza; quello che è sorprendente è che se la matrice ha dimensione n × n, il numero di ripetizioni necessarie per tornare alla matrice di partenza sia P(n), come dimostrò Noel Patson nel 2007.

Vedi anche

Numeri di Fibonacci.

Contattami

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