Thue-Morse Sequence

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

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 taking the ones' 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

(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).

Further infinite product evaluations are given by Tóth (2020). For a complex number with , a Dirichlet series identity is

where is the Riemann zeta function (Tóth 2022, p. 4).

Amazingly, the Thue-Morse sequence can be generated from the substitution system

to obtain

when starting with 0, and

starting with 1. Interpreting these two sequences as binary numbers and writing their values in decimal notation gives the sequences 0, 1, 6, 105, 27030, 1771476585, ... (OEIS A048707) and 1, 2, 9, 150, 38505, 2523490710, ..., respectively. For integer generation , with the initial single symbol designated generation 0, each word has 0s and 1s.

For a nonnegative integer , 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, 1, 1, 0, ... 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),

then satisfies the quadratic equation

This equation has two solutions, and , where is the ones' complement of , i.e.,

which is consistent with the formula for the sum of the roots of a quadratic equation. The quadratic identity for can be demonstrated as follows. Let (...) be a shorthand for the power series

so is (0110100110010110...). To get , simply use the rule for squaring power series over the finite field GF(2)

which extends to the simple rule for squaring a power series

i.e., space the series out by a factor of 2, (0 1 1 0 1 0 0 1 ...), and insert zeros at the odd powers of to get

Then multiply by (which just adds a zero at the front) to get

Adding to gives

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

The sum is the above two sequences XORed together (there are no carries because we're working over the finite field GF(2)), giving

We therefore have

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 nonempty 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 a nonempty word and is its first symbol. 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 at consecutive positions starting with zero-based index 2: 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.

For a positive integer difference , let be the greatest length of an arithmetic progression of indices on which all terms are equal, and let be the least starting index of an arithmetic progression attaining that length. These are called monochromatic arithmetic progressions. An OpenAI Codex project reported the following first-occurrence formulas for integers in the indicated ranges, resolving Conjecture 3.8 of Joshi and Rust (2025).

The maximal lengths were known previously. The reported proofs establish global maximality and exclude every earlier starting index. The first family excludes , for which . As of Oct. 5, 2026, the repository recorded successful Lean builds and an axiom audit, but VibeMathed had not independently rebuilt the package. Independent specialist review of the informal-to-formal correspondence and the complete argument had not been reported (dot 2026, VibeMathed 2026).

Kutsukake et al. (2020) proved that for the prefix word of length , where is a nonnegative integer, a smallest string attractor has four positions for . Faro et al. (2026, pp. 17 and 26) classified these smallest string attractors and found 87 when , 40 when , and 32 for every .