# Golomb’s sequence

Golomb’s sequence is a self-referential ascending order sequence of integers $a$ in which the number of times each number $n$ occurrs is given by $a_{n}$. The sequence begins 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, … (see A001462 in Sloane’s OEIS). For example, $a_{3}=2$ and indeed 3 occurs twice in the sequence. $a_{4}=3$, so 4 occurs thrice.

The recurrence relation for the sequence is $a_{1}=1$ and $a_{n}=a_{n-a_{a_{a_{n-1}}}}+1$. Sometimes recurrence relations for this sequence are given which also explicitly set $a_{2}=2$. The $n$th term of the sequence can be obtained by the calculating $\phi^{2-\phi}n^{\phi-1}$ (with

 $\phi=\frac{1+\sqrt{5}}{2}$

being the golden ratio) and rounding off to the nearest integer. For example, with precision to five decimal places: 1.20178, 1.84448, 2.36975, 2.83087, 3.24948, 3.63706, 4.0006, 4.34477, 4.67284, 4.98724, 5.28984, 5.58209, 5.86518, 6.14005, 6.40753, 6.66827, 6.92286, 7.17178, 7.41548, etc.

Title Golomb’s sequence GolombsSequence 2013-03-22 17:47:07 2013-03-22 17:47:07 PrimeFan (13766) PrimeFan (13766) 4 PrimeFan (13766) Definition msc 03E10 Golomb sequence Silverman’s sequence Silverman sequence