# .

# Golomb sequence

In mathematics, the **Golomb sequence**, named after Solomon W. Golomb (but also called **Silverman's sequence**), is a non-decreasing integer sequence where *a _{n}* is the number of times that

*n*occurs in the sequence, starting with

*a*

_{1}= 1, and with the property that for

*n*> 1 each

*a*is the unique integer which makes it possible to satisfy the condition. For example,

_{n}*a*

_{1}= 1 says that 1 only occurs once in the sequence, so

*a*

_{2}cannot be 1 too, but it can be, 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 OEIS).

*a*_{1} = 1

Therefore 1 occurs exactly one time in this sequence.

*a*_{2} > 1

*a*_{2} = 2

2 occurs exactly 2 times in this sequence.

*a*_{3} = 2

3 occurs exactly 2 times in this sequence.

*a*_{4} = *a*_{5} = 3

4 occurs exactly 3 times in this sequence.

5 occurs exactly 3 times in this sequence.

*a*_{6} = *a*_{7} = *a*_{8} = 4

*a*_{9} = *a*_{10} = *a*_{11} = 5

etc.

Colin Mallows has given an explicit recurrence relation a(1) = 1; a(n+1) = 1 + a(n + 1 - a(a(n))). An asymptotic expression for a_{n} is

\( \varphi^{2-\varphi}n^{\varphi-1}, \)

where φ is the golden ratio.

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. Zbl 1033.11006.

Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. Section E25. ISBN 0-387-20860-7. Zbl 1058.11001.

External links

Python code for Golomb Sequence

Retrieved from "http://en.wikipedia.org/"

All text is available under the terms of the GNU Free Documentation License