# Self-describing Sequence

The sequence $s = [ 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, \dots ]$ may be described as

1 one, 2 twos, 2 ones, 1 two, 1 one, 2 twos, 1 one, etc.

Remarkably, the counts that occur in this description are precisely the elements of $s$ itself! Thus, $s$ is a self-describing sequence.

$\underbrace{1}_{1}\ \underbrace{2\ 2}_{2}\ \underbrace{1\ 1}_{2}\ \underbrace{2}_{1}\ \underbrace{1}_{1}\ \underbrace{2\ 2}_{2}\ \underbrace{1}_{1}\ \underbrace{2\ 2}_{2}\ \underbrace{1\ 1}_{2}\ \underbrace{2}_{1}\ \underbrace{1\ 1}_{2}\ \cdots$

How many twos occur in the first 1,000,000 elements of this sequence?

Bonus: In the original version of this problem, no more than 2000 bytes of memory was to be used during the calculation.

×