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 itself! Thus, is a self-describing sequence.
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? :)