Pages

Thursday, June 26, 2014

Python code for implementing Golomb sequence or Silverman's sequence

Today, I have come across this article in wikipedia. It describes about certain sequence which is surprising to know.
The article is as follows :

"In mathematics, the Golomb sequence, named after Solomon W. Golomb (but also called Silverman's sequence), is a non-decreasing 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 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, 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).
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."

Let us see a python code to implement the same.

The code is given below :

a=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
for i in range(1,45):
    a[1]=1
    a[i+1]=1+a[i+1-a[a[i]]]
    print(a[i])

And here is the answer :
>>>
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
>>> 
Here, I have given n=45, one can change this in the range() and run the code for any other number of iterations.

2 comments:

  1. Hi Mekala.

    Nice post.

    I came across this sequence in a book of programming challenges.

    I like your solution, it uses the recurrence relation, but is hard to understand (unless you understand the derivation of the recurrence).

    Here's another one that's a little easier to understand intuitively: golomb.py.

    It's less efficient but (I think) much more readable.

    ReplyDelete

Receive all updates via Facebook. Just Click the Like Button Below...