Golomb sequence
In mathematics, the Golomb sequence, named after Solomon W. Golomb (but also called Silverman's sequence), is a monotonically increasing integer sequence where an is the number of times that n occurs in the sequence, starting with a1 = 1, and with the property that for n > 1 each an is the smallest unique integer which makes it possible to satisfy the condition. For example, a1 = 1 says that 1 only occurs once in the sequence, so a2 cannot be 1 too, but it can be 2, and therefore must be 2. The first few values 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 (sequence A001462 in the OEIS).
Examples
a1 = 1
Therefore, 1 occurs exactly one time in this sequence.
a2 > 1
a2 = 2
2 occurs exactly 2 times in this sequence.
a3 = 2
3 occurs exactly 2 times in this sequence.
a4 = a5 = 3
4 occurs exactly 3 times in this sequence.
5 occurs exactly 3 times in this sequence.
a6 = a7 = a8 = 4
a9 = a10 = a11 = 5
etc.
Recurrence
Colin Mallows has given an explicit recurrence relation [math]\displaystyle{ a(1) = 1; a(n+1) = 1 + a(n + 1 - a(a(n))) }[/math]. An asymptotic expression for an is
- [math]\displaystyle{ \varphi^{2-\varphi}n^{\varphi-1}, }[/math]
where [math]\displaystyle{ \varphi }[/math] is the golden ratio (approximately equal to 1.618034).
References
- Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas (2003). Recurrence sequences. Mathematical Surveys and Monographs. 104. Providence, RI: American Mathematical Society. pp. 10,256. ISBN 0-8218-3387-1.
- Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. Section E25. ISBN 0-387-20860-7.
External links
 |  |
