Sequenza di Golomb
# 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$ = 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$ = 1 afferma che il numero 1 appare una e una sola volta nella sequenza, perciò $a_2$ 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$ è

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

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

