Thue–Morse sequence

In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is the binary sequence (an infinite sequence of 0s and 1s) obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus far. The first few steps of this procedure yield the strings 0 then 01, 0110, 01101001, 0110100110010110, and so on, which are prefixes of the Thue–Morse sequence. The full sequence begins:

There are several equivalent ways of defining the Thue–Morse sequence.

To compute the n^th element t_n, write the number n in binary. If the number of ones in this binary expansion is odd then t_n = 1, if even then t_n = 0. For this reason John H. Conway et al. call numbers n satisfying t_n = 1 odious (for odd) numbers and numbers for which t_n = 0 evil (for even) numbers. In other words, t_n = 0 if n is an evil number and t_n = 1 if n is an odious number.

This method leads to a fast method for computing the Thue–Morse sequence: start with t₀ = 0, and then, for each n, find the highest-order bit in the binary representation of n that is different from the same bit in the representation of n − 1. (This bit can be isolated by letting x be the bitwise exclusive or of n and n − 1, shifting x right by one bit, and computing the exclusive or of this shifted value with x.) If this bit is at an even index, t_n differs from t_n − 1, and otherwise it is the same as t_n − 1. The resulting algorithm takes constant time to generate each sequence element, using only a logarithmic number of bits (constant number of words) of memory.

The Thue–Morse sequence is the sequence t_n satisfying the recurrence relation

for all non-negative integers n.

The Thue–Morse sequence is a morphic word: it is the output of the following Lindenmayer system:

...
Wikipedia