The Thue-Morse sequence, also called the Morse-Thue sequence or Prouhet-Thue-Morse sequence (Allouche and Cosnard 2000), is one of a number of related sequences of numbers obtained from the parities of the counts of 1's in the binary representation of the nonnegative integers.
The version obtained by directly taking the parities is
|
(1)
|
where
is the binary digit sum. For
, 1, 2, ..., the first few terms are then given by 0, 1,
1, 0, 1, 0, 0, 1, 1, 0, 0, 1, ... (OEIS A010060;
Allouche and Shallit 2003, pp. 15 and 153). An alternate form of the sequence
obtained by the taking the binary complement is given by 1, 0, 0, 1, 0, 1, 1, 0,
0, 1, ... (OEIS A010059; Wolfram 2002, p. 890).
Interpreting the Thue-Morse sequence as concatenated binary digits gives the Thue-Morse constant.
A recurrence plot of the Thue-Morse sequence is illustrated above.
There is an amazing set of products involving the Thue-Morse sequence given by
|
(2)
| |||
|
(3)
| |||
|
(4)
|
(Allouche and Shallit 2003, pp. 153 and 204, factor of two typos corrected), the first of which is due to Woods (1978) and Robbins (1979) and is the special case
of the digit sum identity due to Sondow (2006).
Amazingly, the Thue-Morse sequence can be generated from the substitution system
|
(5)
| |||
|
(6)
|
to obtain
|
(7)
|
when starting with 0, and
|
(8)
|
starting with 1. Interpreting these to sequences as decimal numbers gives the sequences 0, 1, 6, 105, 27030, 1771476585, ... (OEIS A048707)
and 1, 2, 9,1 50, 38505, 2523490710, ..., respectively. After the initial generation,
each subsequence generation has 0s and
1s.
Wolfram (2002) provides various pieces of Wolfram Language code that produce the first terms of the complemented Thue-Morse sequence 1, 0, 0, 1,
0, 0, 1, ... computed as:
1. A substitution system,
2. The position of the evil numbers, which have an even number of 1's in their binary expansion (OEIS A001969),
3. A generating function, following ,
,
4. A cellular automaton (Wolfram 2002, p. 1186),
5. An algebraic generating function,
6. A closed-form expression in terms of a hypergeometric function.
(* 1 *)
Nest[Join[#, 1 - #]&, {1}, k]
(* 2 *)
Table[1 - Mod[DigitCount[n - 1, 2, 1], 2],
{n, 2^k}]
(* 3 *)
(CoefficientList[Product[1 - z^(2^s),
{s, 0, k - 1}], z] + 1)/2
(* 4 *)
Flatten[CellularAutomaton[{69540422, 2, 2},
{{1}, 0}, 2^k - 1, {All, 0}]]
(* 5 *)
Mod[CoefficientList[Series[(1 + Sqrt[(1 - 3 x)/
(1 + x)])/(2 (1 + x)), {x, 0, 2^k - 1}], x], 2]
(* 6 *)
Mod[Table[(-1)^n/2 + (-3)^n Sqrt[Pi] *
Hypergeometric2F1Regularized[3/2, - n, 3/2 - n, - 1/3]/
(4 n!), {n, 0, 2^k - 1}], 2]
Writing the sequence as a power series over the finite field GF(2),
|
(9)
|
then
satisfies the quadratic equation
|
(10)
|
This equation has two solutions, and
, where
is the complement of
, i.e.,
|
(11)
|
which is consistent with the formula for the sum of the roots of a quadratic. The equality (10) can be demonstrated as follows. Let (...) be a shorthand for the power
series
|
(12)
|
so
is (0110100110010110...). To get
, simply use the rule for squaring power
series over GF(2)
|
(13)
|
which extends to the simple rule for squaring a power series
|
(14)
|
i.e., space the series out by a factor of 2, (0 1 1 0 1 0 0 1 ...), and insert zeros in the odd places to get
|
(15)
|
Then multiply by
(which just adds a zero at the front) to get
|
(16)
|
Adding to
gives
|
(17)
|
This is the first term of the quadratic equation, which is the Thue-Morse sequence with each term doubled up. The next term is , so we have
|
(18)
| |||
|
(19)
|
The sum is the above two sequences XORed together (there are no carries because we're working over GF(2)), giving
|
(20)
|
We therefore have
 |
(21)
|
The Thue-Morse words are overlapfree (Allouche and Shallit 2003, p. 15), and therefore also cubefree
on two symbols (Morse and Hedlund 1944). The sequence therefore contains no substrings
of the form , where
is any word. For example, it does
not contain the words 000, 010101 or 010010010. In fact,
the following stronger statement is true: the Thue-Morse sequence does not contain
any substrings of the form
, where
is the first symbol of
. We can obtain a squarefree
sequence on three symbols by doing the following: take the Thue-Morse sequence 0110100110010110...
and look at the sequence of words of length 2 that appear:
10 01 10 00 01 11 10 .... Replace 01 by 0, 10 by 1, 00 by 2 and 11 by 2 to get the
following: 1012021.... Then this sequence is squarefree
(Morse and Hedlund 1944).
The Thue-Morse sequence has important connections with the Gray code. Kindermann generates fractal music using the self-similarity of the Thue-Morse sequence.