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.

×

Problem Loading...

Note Loading...

Set Loading...