In mathematics, the Golomb sequence, named after
Solomon W. Golomb (but also called Silverman's sequence), is a
monotonically increasing
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order ...
integer sequence
In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers.
An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. For ...
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
n'' is the smallest unique integer which makes it possible to satisfy the condition. For example, ''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 .
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
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
. An
asymptotic expression for ''a
n'' is
:
where
is the
golden ratio
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities a and b with a > b > 0,
where the Greek letter phi ( ...
(approximately equal to 1.618034).
References
*
* {{cite book , last=Guy , first=Richard K. , authorlink=Richard K. Guy , title=Unsolved problems in number theory , publisher=
Springer-Verlag
Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing.
Originally founded in 1842 in ...
, edition=3rd , year=2004 , isbn=0-387-20860-7 , zbl=1058.11001 , at=Section E25
External links
Python code for Golomb Sequence
Integer sequences
Golden ratio