# 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 smallest 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 the OEIS).

## Examples

*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.

## 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 *a _{n}* 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

Original source: https://en.wikipedia.org/wiki/ Golomb sequence.
Read more |