Generate a Kolakoski sequence Definition1


  A Kolakoski sequence is a self-describing infinite sequence {kn} of alternating blocks of 1's and 2's, given by the following rules: 
  
  
  k0 = 1
  kn = the length of the (n+1)'th block
  


The Task

Given a positive integer n, generate the first n elements of the Kolakoski sequence.

Details

Input will be provided as a single command line argument n. Please write a full program that will print the first n elements of the Kolakoski sequence (in order) to STDOUT, with each element separated by your favorite whitespace.

Scoring

Lets count source code bytes this time with all whitespace included. Fewest number of bytes wins. In the event of a tie, the solution with the earliest submission time wins.

The Sequence2

1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, ...


References



John Smith, Ariel Scolnicov, yark. "Kolakoski sequence" (version 3). PlanetMath.org. Freely available at http://planetmath.org/KolakoskiSequence.html.


The Online Encyclopedia of Integer Sequences http://oeis.org/A000002



Other resources


Kolakoski Sequence at Wikipedia http://en.wikipedia.org/wiki/Kolakoski_sequence
Kolakoski Sequence at Wolfram MathWorld http://mathworld.wolfram.com/KolakoskiSequence.html
J - 23 char

A little late to the party, but I'd like to bust out a neat little J trick here.

1($1+2|I.)^:_~".&gt;2{ARGV


Given input N, this verb operates by executing N&amp;($1+2|I.) on a starting argument of 1 until it reaches a fixed point. If the item at index i in y is n, there will be n copies of i in I.y, so for instance I. 0 1 1 0 0 3 1 is 1 2 5 5 5 6. We mod the result of that by 2 and add one. Then, x $ y forces y into a list of length x, truncating it or extending it cyclically as necessary.

So here's what happens when the input is, say, 10.

   10 ($1+2|I.)^:a: 1
1 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2 1 2
1 2 2 1 2 2 1 2 2 1
1 2 2 1 1 2 1 1 2 2
1 2 2 1 1 2 1 2 2 1


We start with a row of all 1s and then "settle down" into the Kolakoski sequence. First, it turns into 1 2 1 2 1 2... as each contiguous block of ones or twos is described by length 1. Then we apply it again and it turns into 1 2 2 1 2 2 1 2 2... since the ones are described by 1 and the twos are described by 2. The we continue again and again until we see there is no change, at which point we stop and give the result.

Other "self-describing" sequences can be similarly derived in J using I. and ^:_.



Edit

Over a year ago, @ardnew asked:


  what is the relationship between n and the number of those intermediate iterations required to generate the sequence of length n?


To make sure we're on the same page, I consider the calculation for n = 10 above to have taken 5 iterations.

If there are s terms settled at the i-th iteration for n, then at the (i+1)-th iteration, there will be (at least) k0 + k1 + ... + ks + 1 terms settled. The '+ 1' appears because the next term will also be correct, since it must be and is different from the term before it.

So if K(s) is the sequence of partial sums of kn, then we can lower bound the number of iterations for n by the least a such that (1+K)a(1) ≥ n. I don't how to prove we don't accidentally do a bit better (by picking up more correct terms than we expected in some iteration), but according to the numbers, we don't:

   k =: ($ 1 + 2 | I.)^:_&amp;1               NB. Kolakoski seq
   pk =: +/\ @: k                         NB. partial sums ("K")
   ((1 + pk 2000) {~ &lt;:) ::_:^:(i.20) 1   NB. iterating 1+K, say, 20 times
1 2 4 7 11 18 28 43 65 99 150 226 340 511 768 1153 1728 2590 _ _
   NB. compare with observed number of settled terms up to 2000:
   +/"1 }. (k &lt;./\ . ="1 ($1+2|I.)^:a:&amp;1) 2000
1 2 4 7 11 18 28 43 65 99 150 226 340 511 768 1153 1728 2000


The underscores are index errors (:: _:), telling us 20 iterations is too much for the first 2000 terms of kn to handle.