Golomb sequence explained

In mathematics, the Golomb sequence, named after Solomon W. Golomb (but also called Silverman's sequence), is a monotonically increasing integer sequence where a_n is the number of times that n occurs in the sequence, starting with a₁ = 1, and with the property that for n > 1 each a_n is the smallest unique integer which makes it possible to satisfy the condition. For example, a₁ = 1 says that 1 only occurs once in the sequence, so a₂ 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 .

Examples

a₁ = 1
Therefore, 1 occurs exactly one time in this sequence.

a₂ > 1
a₂ = 2

2 occurs exactly 2 times in this sequence.
a₃ = 2

3 occurs exactly 2 times in this sequence.

a₄ = a₅ = 3

4 occurs exactly 3 times in this sequence.
5 occurs exactly 3 times in this sequence.

a₆ = a₇ = a₈ = 4
a₉ = a₁₀ = a₁₁ = 5

etc.

Recurrence

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

\varphi is the golden ratio (approximately equal to 1.618034).

References

• Book: Everest . Graham . van der Poorten . Alf . Shparlinski . Igor . Ward . Thomas . Recurrence sequences . Mathematical Surveys and Monographs . 104 . . . 2003 . 0-8218-3387-1 . 1033.11006 . 10,256 .
• Book: Guy, Richard K. . Richard K. Guy

. Richard K. Guy . Unsolved problems in number theory . . 3rd . 2004 . 0-387-20860-7 . 1058.11001 . Section E25 .

External links

• Python code for Golomb Sequence