5
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the link! Now I know what it's called! Golomb's sequence! \$\endgroup\$ – aliqandil Mar 25 '16 at 19:21
  • \$\begingroup\$ Welp!! I searched "Golomb's sequence" and this is a duplicate i think. \$\endgroup\$ – aliqandil Mar 25 '16 at 19:23
  • \$\begingroup\$ @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. \$\endgroup\$ – Peter Taylor Mar 25 '16 at 19:27
1
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.