Thue–Morse sequence

Remarks

Check: $t_5 = 0$ because $5 = 101_2$ has two digits $1$, and $t_7 = 1$ because $7 = 111_2$ has three.

The sequence is the fixed point, starting with $0$, of the morphism $\mu$ of words with $\mu(0) = 01$ and $\mu(1) = 10$. So the first $2^{m+1}$ terms are the first $2^m$ terms followed by their complement, where $0$ and $1$ are swapped.

The sequence is overlap-free: it has no factor of the form $a x a x a$, where $a$ is a letter and $x$ is a word. In particular it has no factor of the form $u u u$ with $u$ nonempty. Thue proved overlap-freeness, and it makes the sequence a basic example in combinatorics on words. It is not periodic, and it is a $2$-automatic sequence, computed by a finite automaton that reads $n$ in base $2$.