In mathematics, the Thue–Morse or Prouhet–Thue–Morse sequence is the binary sequence (an infinite sequence of 0s and 1s) that can be obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus far. It is sometimes called the fair share sequence because of its applications to fair division or parity sequence. The first few steps of this procedure yield the strings 0, 01, 0110, 01101001, 0110100110010110, and so on, which are the prefixes of the Thue–Morse sequence. The full sequence begins:
01101001100101101001011001101001... The sequence is named after Axel Thue, Marston Morse and (in its extended form) Eugène Prouhet.
Definition There are several equivalent ways of defining the Thue–Morse sequence.
Direct definition
To compute the nth element tn, write the number n in binary. If the number of ones in this binary expansion is odd then tn = 1, if even then tn = 0. That is, tn is the even parity bit for n. John Conway et al. deemed numbers n satisfying tn = 1 to be odious (intended to be similar to odd) numbers, and numbers for which tn = 0 to be evil (similar to even) numbers.
Fast sequence generation This method leads to a fast method for computing the Thue–Morse sequence: start with t0 = 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. If this bit is at an even index, tn differs from tn−1, and otherwise it is the same as tn−1. In Python:
The resulting algorithm takes constant time to generate each sequence element, using only a logarithmic number of bits (constant number of words) of memory.
Recurrence relation The Thue–Morse sequence is the sequence tn satisfying the recurrence relation
t 0 = 0 , t 2 n = t n , t 2 n + 1 = 1 − t n , {\displaystyle {\begin{aligned}t_{0}&=0,\\t_{2n}&=t_{n},\\t_{2n+1}&=1-t_{n},\end{aligned}}}
for all non-negative integers n.
L-system
The Thue–Morse sequence is a morphic word: it is the output of the following Lindenmayer system:
Characterization using bitwise negation The Thue–Morse sequence in the form given above, as a sequence of bits, can be defined recursively using the operation of bitwise negation. The first element is 0. Once the first 2n elements have been specified, forming a string s, then the next 2n elements must form the bitwise negation of s. Now we have defined the first 2n+1 elements, and we recurse. Spelling out the first few steps in detail:
We start with 0. The bitwise negation of 0 is 1. Combining these, the first 2 elements are 01. The bitwise negation of 01 is 10. Combining these, the first 4 elements are 0110. The bitwise negation of 0110 is 1001. Combining these, the first 8 elements are 01101001. And so on. So
T0 = 0. T1 = 01. T2 = 0110. T3 = 01101001. T4 = 0110100110010110. T5 = 01101001100101101001011001101001. T6 = 0110100110010110100101100110100110010110011010010110100110010110. And so on. In Python:
Which can then be converted to a (reversed) string as follows:
Generating function A generating function for the sequence can be defined by:
∏ i = 0 ∞ ( 1 − x 2 i ) = ∑ j = 0 ∞ ( − 1 ) t j x j , {\displaystyle \prod _{i=0}^{\infty }\left(1-x^{2^{i}}\right)=\sum _{j=0}^{\infty }(-1)^{t_{j}}x^{j},}
where tj is the jth element if we start at j = 0.
… excerpt ends here. Continue reading the full article.
