# Golomb's sequence to 1000000 [duplicate]

This used to be an old Computer Olympiad Question, not sure what the actual source was.

Assume function f:

• f(1) = 1
• This f(1), f(2), f(3), f(4), ... sequence of numbers are in ascending order.
• Number n has been repeated f(n) times

Here is the sequence up to the fifteenth number:

n :     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
f(n) :  1 2 2 3 3 4 4 4 5  5  5  6  6  6  6


for example number 4 has been repeated f(4) = 3 times.

So what you should do is to print out the sequence till f(1000000). There are no inputs.

Also you can run out of memory, not an issue! Code with less bytes wins.

So this is how to output will look like: 1 2 2 3 3 4 4 4 5 ...

## CJam (22 bytes)

1{_~$(~$-)~$)}A6#(/]S*  Online demo for only 15 terms This relies on one of the formulae given in the entry for OEIS A001462, and the use of ~$ to index the stack from the bottom.

• Thanks for the link! Now I know what it's called! Golomb's sequence! – aliqandil Mar 25 '16 at 19:21
• Welp!! I searched "Golomb's sequence" and this is a duplicate i think. – aliqandil Mar 25 '16 at 19:23
• @aliqandil, I thought it rang a bell, but I searched for A001462 and found nothing so I went ahead and wrote an answer. Obviously we weren't as consistent in adding OEIS references back in 2012. I probably shouldn't use my binding vote to close as a dupe given that I've got rep from an answer. – Peter Taylor Mar 25 '16 at 19:27

# Ruby, 55 bytes

Dynamic programming-style solution. Generates the table iteratively, and then prints the needed terms.

f,i=[0],0
f+=[i+=1]*(f[i]||i)while f.size<1e6
p f[1,1e6]


# MATL, 25 22 bytes

FTTQ@2+yy)1X"!htn1e7<


Try it online replacing 1e7 in the code by a more manageable number, such as 1e2

This initiallizes the sequence as [1 2 2]`, and from that builds the rest of the sequence applying its definition.