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.


Source: A computer programming contest between Dutch students and professionals a long time ago (1996 or 1997 if I remember correctly.) Our team was the only team to get this problem right, and that within the first five minutes of the contest. Can you beat our record? :)
×

Problem Loading...

Note Loading...

Set Loading...