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 ${\varphi }^{2-\varphi }{n}^{\varphi -1}$ (with

$$\varphi =\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
Canonical name	GolombsSequence
Date of creation	2013-03-22 17:47:07
Last modified on	2013-03-22 17:47:07
Owner	PrimeFan (13766)
Last modified by	PrimeFan (13766)
Numerical id	4
Author	PrimeFan (13766)
Entry type	Definition
Classification	msc 03E10
Synonym	Golomb sequence
Synonym	Silverman’s sequence
Synonym	Silverman sequence