Golomb's Sequence

 

Definition

Golomb's sequence, named after Solomon Golomb, is a curious sequence of whole numbers that describes itself. It is defined in the following way: it is a non-decreasing sequence of whole numbers where the nth term gives the number of times n occurs in the sequence, and the first term is 1. From this we can begin constructing it: The second element must be greater than 1 as there is only one 1. It must be 2, and so must be the third element. Given this, there must be 2 threes, and from here on we may merely refer to the terms in the sequence and continue from there. The first several terms of the sequence are: \[ 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,... \]

Recurrence Relation

The sequence can be given an explicit recurrence relation by stating it in the following way, using the self-describing property: To determine the next term in the sequence, go back the number of times that the previous term occurred (this will put you at the next-smallest value), then add one. For example, to determine the 12 term (6), count the number of times that the value of the 11th term (5) occurs (3 times). Step back that many terms (to the 9th term: 5) then add one to that value (6). This then gives the recurrence relation: \[ a(n+1)=1+a\left ( n+1-a(a(n)) \right ) \] Where \(a(1)=1\).

Asymptotic Behavior

The recurrence relation allows us to give an asymptotic expression for the value of the sequence. Let us suppose the sequence grows like \[ a(n)=A n^\alpha \] Let us put this into the recurrence relation: \[ A(n+1)^\alpha=1+A\left ( n+1-A(A n^\alpha)^\alpha \right )^\alpha \] Simplifying and rearranging, we obtain: \[ 1=\frac{1}{A(n+1)^\alpha}+\left (1-A^{1+\alpha}\frac{n^{\alpha^2}}{n+1} \right )^\alpha \] As \(\alpha<1\), \(\frac{n^{\alpha^2}}{n+1}\) goes to zero. For small x, \((1+x)^b\rightarrow 1+bx\). Thus, asymptotically: \[ 1\approx\frac{1}{A(n+1)^\alpha}+1-\alpha A^{1+\alpha}\frac{n^{\alpha^2}}{n+1} \] \[ \alpha A^{2+\alpha}n^{\alpha^2}(n+1)^{\alpha-1} \approx 1 \] Thus it must be the case that \[ \alpha^2+\alpha-1=0 \] \[ A=\alpha^{-\frac{1}{2+\alpha}} \] The solution to the first equation is \[ \alpha=\left \{\varphi-1,-\varphi \right \} \] Where \(\varphi\) is the golden ratio. As the exponent is clearly positive, we find the sequence is asymptotic to: \[ a(n)\rightarrow \varphi^{2-\varphi}n^{\varphi-1} \] Below we plot the ratio of these two expressions: