the Thue-Morse sequence

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

1. For each nonnegative integer $n$ , let $\alpha_n=0$ if the number of $1$ ‘s in the binary representation of $n$ is even, and $\alpha_n=1$ 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 $0$ s and $1$ s interchanged.
i.e. Start with $0$ . Append $1$ to that. $\to 01$ .
Append $10$ to that $\to 0110$ .
Append $1001$ to that $\to 01101001$ .
Append $10010110$ to that $\to 0110100110010110$ . etc.

3. Start with $0$ . Apply $0\to 01$ and $1\to 10$ .

If $n$ is $\overline{ab\dots c}$ in binary notation, then $2n=\overline{ab\dots c0}$ , with the same number of binary $1$ s as $n$ , and $2n+1=\overline{ab\dots c1}$ , containing one more $1$ . So:

$\alpha_{2n}=\alpha_n \quad \text{ and } \quad \alpha_{2n+1}=1-\alpha_{2n} \quad \text{ for } n=1,2,\dots$

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, $0.0110100110010110\dots=0.4124\dots$ , the Morse-Thue constant, it’s intimately related to period-doubling bifurcation and the Mandelbrot set.

The Tarry-Escott problem

Can the set $\{0,1,2,3,\dots,2^{k+1}-1\}$ be partitioned into two disjoint subsets $\{x_1,x_2,\dots,x_{2^k}\}$ and $\{y_1,y_2,\dots,y_{2^k} \}$ such that

$\sum_{i=1}^{2^k} x_i^a=\sum_{i=1}^{2^k} y_i^a \quad \text{for all a=0,1,2,\dots,k?}$

The Thue-Morse sequence determines such a partitioning.
Let $X_k$ be the set of all $n \in \{ 0,1,2,\dots,2^{k+1}-1\}$ with $\alpha_n=0$ ,
and $Y_k$ be the set of $n \in \{ 0,1,2,\dots,2^{k+1}-1\}$ with $\alpha_n=1$ .

e.g. Take $k=3$ .
The first 16 terms of the sequence are $0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0$ , so
$X_n = \{0,3,5,6,9,10,12, 15\}$ , and $Y_n = \{1,2,4,7,8,11,13, 14\}$ .
And sure enough…
$0^0+3^0+5^0+6^0+9^0+10^0+12^0+15^0=1^0+2^0+4^0+7^0+8^0+11^0+13^0+14^0$ ,
$0^1+3^1+5^1+6^1+9^1+10^1+12^1+15^1=1^1+2^1+4^1+7^1+8^1+11^1+13^1+14^1$ ,
$0^2+3^2+5^2+6^2+9^2+10^2+12^2+15^2=1^2+2^2+4^2+7^2+8^2+11^2+13^2+14^2$ ,
$0^3+3^3+5^3+6^3+9^3+10^3+12^3+15^3=1^3+2^3+4^3+7^3+8^3+11^3+13^3+14^3$ .