Note: I come from a mathematics background.
The Thue-Morse sequence $t_n$ is a binary sequence that takes the value $0$ at the positive integer $n$ if the number of $1$s in its binary expansion is even, $1$ otherwise.
A definition that is closer to computer science states that $t_n$ is the binary sequence obtained by starting with $0$ and successively appending the boolean complement of the sequence obtained so far.
Thus, $t_n$ begins $0,1,1,0,1,0,0,1,\ldots$
This sequence is of much interest in mathematics, but so far I have not come across any applications in computer science. This surprises me, for the two following reasons:
- The Thue-Morse sequence is automatic, i.e., the sequence is fully characterized by a finite automaton,
- It is a binary sequence.
What theoretic or practical applications of the Thue-Morse sequence are there in computer science?