# Self-describing Sequence

**Computer Science**Level 5

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? :)

**Your answer seems reasonable.**Find out if you're right!

**That seems reasonable.**Find out if you're right!

Already have an account? Log in here.