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

Lucas generalizzati (numeri di)

Sequenze 

Le sequenze di Lucas generalizzate sono generalizzazioni delle sequenze di Fibonacci e di Lucas.

Scelti due interi P e Q non nulli e primi tra loro, si definisce la sequenza di Lucas come U0(P, Q) = 0, U1(P, Q) = 1, Un + 1(P, Q) = PUn(P, Q) – QUn – 1(P, Q) e la sequenza associata come V0(P, Q) = 2, V1(P, Q) = P, Vn + 1(P, Q) = PVn(P, Q) – QVn – 1(P, Q).

Alcuni esempi notevoli:

  • per P = 1 e Q = –1 la sequenza ottenuta e quella dei numeri di Fibonacci, mentre la sequenza associata è quella dei numeri di Lucas;

  • per P = 2 e Q = –1 la sequenza ottenuta e quella dei numeri di Pell, mentre la sequenza associata è quella dei numeri di Pell – Lucas;

  • Un(k + 1, k) = (k^n – 1) / (k – 1) e Vn(k + 1, k) = kn + 1 e in particolare, Un(3, 2) = 2n – 1 e Vn(3, 2) = 2n + 1.

 

Definendo D = P2 – 4Q, la sequenza di Lucas si può ottenere come Formula per il calcolo dei numeri di una sequenza di Lucas e la sequenza associata come Vn(P, Q) = αn + βn, dove Formula per il calcolo di α e Formula per il calcolo di β.

 

I numeri che formano una sequenza di Lucas sono chiamati “numeri di Lucas generalizzati”, ma anche talvolta semplicemente “numeri di Lucas”.

 

Per le sequenze di Lucas e le loro associate valgono numerose relazioni, generalizzazioni di quelle dei numeri di Fibonacci e Lucas. Per esempio:

  • Um + n = UmVnQnUmn;

  • Vm + n = VmVnQnVmn;

  • U2n = UnVn;

  • Formula che coinvolge numeri di Lucas generalizzati.

 

Vi sono formule più semplici per il calcolo dei numeri di Lucas generalizzati per alcuni valori particolari di P e Q. In particolare se P = 1:

  • Formula per il calcolo di numeri di Lucas generalizzati;

  • Formula per il calcolo di numeri di Lucas generalizzati;

  • Formula per il calcolo di numeri di Lucas generalizzati;

  • Formula per il calcolo di numeri di Lucas generalizzati;

  • Formula per il calcolo di numeri di Lucas generalizzati.

 

Se invece Q = –1:

  • Formula per il calcolo di numeri di Lucas generalizzati;

  • Formula per il calcolo di numeri di Lucas generalizzati;

  • Formula per il calcolo di numeri di Lucas generalizzati;

  • Formula per il calcolo di numeri di Lucas generalizzati;

  • Formula per il calcolo di numeri di Lucas generalizzati, per n pari;

  • Formula per il calcolo di numeri di Lucas generalizzati, per n dispari;

  • Formula per il calcolo di numeri di Lucas generalizzati;

  • Formula per il calcolo di numeri di Lucas generalizzati.

 

Se p è un numero primo dispari che non divide DQ, valgono le seguenti congruenze, nelle quali Simbolo di Jacobi (D | p) rappresenta il simbolo di Jacobi, (v. anche pseudoprimi di Lucas (I)):

  • Congruenza soddisfatta da un primo dispari p;

  • Congruenza soddisfatta da un primo dispari p;

  • VnP mod n;

  • Congruenza soddisfatta da un primo dispari p.

Se p è primo rispetto a 2DPQ, tra le prime tre congruenze due implicano la restante.

L’ultima congruenza è sempre soddisfatta se p è il quadrato di un primo q, Q = 1 e D è un residuo quadratico modulo q (Robert Baillie e Samuel S. Wagstaff Jr., 1980).

 

Se p è primo e non divide DQ, Congruenza soddisfatta da un primo p, dove Simbolo di Jacobi (Q | p) è il simbolo di Jacobi, e Congruenza soddisfatta da un primo p (Hugh Williams).

 

|P2 – 2Q| è 0, Q o 2Q, la sequenza è degenere. Nel 1954 Ward dimostrò che i numeri della sequenza hanno, tra loro, infiniti fattori primi distinti se e solo se la sequenza non è degenere.

 

Si dice che un numero di Lucas generalizzato Un ha un divisore primitivo se è divisibile per un numero primo che non divide alcun altro Uk con 0 < k < n e (α – β)2 ≠ D. Il problema di determinare quali numeri di Lucas generalizzati abbiano divisori primitivi ha richiesto un secolo per una soluzione completa.

Due coppie di numeri (α, β) e (α’, β’) si dicono “equivalenti” se α / β = α’ / β’; due coppie equivalenti generano numeri di Lucas generalizzati privi di divisori primitivi per gli stessi valori di n, quindi nella ricerca si considerano solo coppie non equivalenti.

 

Il primo passo si deve a K. Zsigmondy, che nel 1892 dimostrò che se α e β sono interi, Un ha un divisore primitivo per n > 6 (v. numeri di Lehmer (I)).

 

Nel 1913 P.D. Carmichael dimostrò che se α e β sono reali, Un ha un divisore primitivo per n > 12.

 

Un grande progresso si deve a Andrzej Schinzel, che nel 1962 dimostrò che se α e β sono complessi, Un ha un divisore primitivo per n abbastanza grande.

Nel 1974 lo stesso Schinzel dimostrò che esiste un valore n0 indipendente da α e β, tale che per n > n0 Un ha un divisore primitivo. C. Stewart dimostrò nel 1977 che n0 ≤ 467e452 ≈ 4.3563748210 • 10236; P.M Voutier ridusse il limite a 2 • 1010 nel 1995 e a 30010 l’anno seguente.

Stewart dimostrò anche che, considerando tutti i valori di α e β, per n > 6 e diverso da 8, 10 e 12 i numeri di Lehmer privi di divisori primitivi sono in numero finito, mentre esistono infinite eccezioni per gli altri valori di n. Il metodo di Stewart permette di trovare tutte le eccezioni, fissato n.

 

Utilizzando il metodo di Stewart, P.M. Voutier completò nel 1995 l’elenco dei numeri di Lucas generalizzati senza divisori primitivi per n ≤ 30, a meno di equivalenze, mostrato nella tabella seguente, nella quale k e m rappresentano numeri naturali.

n

(P, D)

Un

1

Tutti

1

2

(1, 1 – 4m) per m diverso da 1, (2k, 4k – 4m) per m dispari e k e m non entrambi uguali a 1

1 – m, 4km

3

(m, 4 – 3m2) per m > 1, (m, 4 · 3k – 3m2) per m non multiplo di 3 ed escluso il caso k = 1 e m = 2

1, 3k

4

(m, 2 – m2) per m dispari e maggiore di 1, (m, 4 – m2) per per m pari e maggiore di 2

m, 2m

5

(1, 5), (1, –7), (1, –11), (1, –15), (2, –40), (12, –76), (12, –1364)

5, –1, 1, 5, 5, 1, 1

6

Valori di P e D per i quali non si hanno divisori primitivi per m non multiplo di 3 e maggiore di 4, Valori di P e D per i quali non si hanno divisori primitivi per m multiplo di 3, Valori di P e D per i quali non si hanno divisori primitivi per m dispari e non multiplo di 3, Valori di P e D per i quali non si hanno divisori primitivi per m dispari e multiplo di 3

Valore di U(n) senza divisori primitivi, m(2m2 + 3), Valore di U(n) senza divisori primitivi, m(2k + 1m2 + 3 · 4k)

7

(1, –7), (1, –19)

7, 1

8

(1, –7), (2, –24)

–3, –40

10

(2, –8), (5, –3), (5, –47)

–22, –3725, 10025

12

(1, 5), (1, –7), (1, –11), (1, –15), (1, –19), (2, –56)

144, 45, 160, –231, –3024, –23452

13

(1, –7)

–1

18

(1, –7)

85

30

(1, –7)

–24475

 

Finalmente nel 1999 Yuri Bilu, Guillaume Hanrot e Paul M. Voutier dimostrarono che non esistono numeri di Lucas generalizzati senza divisori primitivi per n > 30, e che quindi l’elenco sopra riportato è completo.

 

Le sequenze di Lucas generalizzate sono legate ai numeri di Lehmer (I), perché se Ln è il termine n-esimo della sequenza di Lehmer generata dagli stessi valori di α e β:

  • se n è dispari, Ln = Un;

  • se n è pari, Ln = (α + β)Un;

  • un primo p è un divisore primitivo di Ln se e solo se è divisore primitivo di Un.

 

Contattami

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