# the Thue-Morse sequence

A non-periodic sequence of s and s, with no 3 consecutive identical blocks of any length.
Ways of constructing it:

1. For each nonnegative integer , let if the number of ‘s in the binary representation of is even, and if this number is odd. (Conway calls these evil and odious numbers, respectively)

2. At each step, append a copy of the sequence so far, with s and s interchanged.
Append to that .
Append to that .
Append to that . etc.

If is in binary notation, then , with the same number of binary s as , and , containing one more . So:

i.e. the sequence is determined by its odd-numbered terms, and each of those is different to the previous (even) term.

Interpreted as a binary fraction, , the Morse-Thue constant, it’s intimately related to period-doubling bifurcation and the Mandelbrot set.

The Tarry-Escott problem

Can the set be partitioned into two disjoint subsets and such that

The Thue-Morse sequence determines such a partitioning.
Let be the set of all with ,
and be the set of with .

e.g. Take .
The first 16 terms of the sequence are , so
, and .
And sure enough…
,
,
,
.

This works for any polynomial of degree .
If if a polynomial of degree not exceeding , then