The OEIS sequence A000002

The sequences in The On-Line Encyclopedia of Integer Sequences® are themselves arranged into a sequence, each being indexed by Axxxxxx. Hence, the sequence
2, 3, 2, 1, 3, 4, 1, 7, 7, 5, 45, 2, 181, 43, 17, ...
can never be included in the encyclopedia: its definition is $a_n=1+\text{nth term of the nth sequence in the OEIS}$.

By the way, which sequences have the honor of being on the virtual first page of the OEIS? A000004 consists of zeros. Its description offers the following explicit formula:

a(n)=A*sin(n*Pi) for any A. [From Jaume Oliver Lafont, Apr 02 2010]

The sequence A000001 counts the groups of order n.

The sequence A000002 consists of 1s and 2s only:
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, ...
The defining property of this sequence is self-similarity: consider the runs of equal numbers
1, 22, 11, 2, 1, 22, 1, 22, 11, 2, 11, 22, 1, 2, 11, 2, 1, 22, 11, ...
and replace each run by its length:
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, ...
You get the original sequence again.

This is the Kolakoski sequence, which first appeared in print in 1965. Contrary to what one might expect from such a simple definition, there is no simple pattern; it is not even known whether 1s and 2s appear with the same asymptotic frequency 1/2. One way to look for patterns in a function/sequence is to take its Fourier transform, and this is what I did below:

Specifically, this is the absolute value of $\displaystyle F(t)=\sum_{n=1}^{500} (2a_n-3) e^{2\pi i n t}$. To better see where the peaks fall, it’s convenient to look at $|F(1/t)|$:

Something is going on at $t=1/3$, i.e. at period 3. Recall that the sequence contains no triples 111 or 222: there are no runs of more than 2 equal numbers. So perhaps it’s not surprising that a pattern emerges at period 3. And indeed, even though the percentage of 1s among the first 500 terms of the sequence is 49.8%, breaking it down by n mod 3 yields the following:

• Among $a_{3k}$, the percentage of 1s is 17.4%
• Among $a_{3k+1}$, the percentage of 1s is 85.2%
• Among $a_{3k+2}$, the percentage of 1s is 46.8%

Noticing another peak at $t=1/9$, I also broke down the percentages by n mod 9:

• $n=9k$: there are 5.4% 1s
• $n=9k+1$: there are 74.8% 1s
• $n=9k+2$: there are 41.4% 1s
• $n=9k+3$: there are 21.6% 1s
• $n=9k+4$: there are 97.2% 1s
• $n=9k+5$: there are 70.2% 1s
• $n=9k+6$: there are 25.2% 1s
• $n=9k+7$: there are 84.6% 1s
• $n=9k+8$: there are 28.8% 1s

Nothing close to 50%…

In conclusion, my code for the Kolakoski sequence. This time I used Maple (instead of Scilab) for no particular reason.

N:=500; ks:=Array(1..N+2); i:=0; j:=1; new:=1; while i<=N do i:=i+1; ks[i]:=new; if (ks[j]=2) then i:=i+1; ks[i]:=new; end if; j:=j+1; new:=3-new; end do: