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

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.

Hi Mekala.

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

ey very nice blog!!..

ReplyDeleteEclectroic Cadd Traning Center

Bets Architecture designing

Mechanical cadd center