Sequenza di Golomb

In matematica, la sequenza di Golomb, che prende il nome dal matematico e ingegnere americano Solomon W. Golomb, è una successione di interi monotona non decrescente nella quale a_n rappresenta il numero di volte in cui n compare nella successione stessa. La successione inizia con a₁ = 1 e ha la proprietà che, per qualsiasi n > 1, a_n è il primo e unico intero che soddisfa la definizione. Ad esempio, il termine a₁ = 1 afferma che il numero 1 appare una e una sola volta nella sequenza, perciò a₂ non può essere anch'esso 1, ma può (e deve) essere l'intero successivo, 2. I primi termini della sequenza di Golomb sono

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12...

Relazione di ricorrenza

Colin Mallows ha ottenuto una relazione di ricorrenza esplicita per gli elementi della sequenza di Golomb:

$a(1)=1;a(n+1)=1+a(n+1-a(a(n)))$.

Una stima asintotica per a_n è

${\phi }^{2-\phi }{n}^{\phi -1},$

dove $\phi$ è il valore della sezione aurea (approssimativamente 1.618034).

Bibliografia

• Template:Cita libro

Collegamenti esterni

• Template:OEIS
• Un codice Python per calcolare la sequenza di Golomb