Thue Morse Sequence Generator

What is the Thue-Morse Sequence?

The Thue-Morse sequence (also known as the Prouhet-Thue-Morse sequence) is an infinite binary sequence of 0s and 1s that is self-similar and contains no overlapping patterns. It is named after the French mathematician Eugène Prouhet, who first used it in 1851, and the Norwegian mathematician Axel Thue, who studied it systematically in 1906.

How is the Thue-Morse Sequence Defined?

There are several equivalent ways to define the Thue-Morse sequence:

• Binary Parity: The $n$-th term $t_n$ (for $n \ge 0$) is determined by the number of ones in the binary representation of $n$. If $n$ contains an even number of ones, $t_n = 0$. If it contains an odd number of ones, $t_n = 1$.
  For example:
  • $n = 0$ (binary $0$) has $0$ ones (even) $\implies t_0 = 0$.
  • $n = 1$ (binary $1$) has $1$ one (odd) $\implies t_1 = 1$.
  • $n = 2$ (binary $10$) has $1$ one (odd) $\implies t_2 = 1$.
  • $n = 3$ (binary $11$) has $2$ ones (even) $\implies t_3 = 0$.
• Complementary Morphism: Start with the term $0$. To generate the next generation, append the boolean complement of the current sequence.
  • $T_0 = 0$
  • $T_1 = 01$ (append complement of $0$, which is $1$)
  • $T_2 = 0110$ (append complement of $01$, which is $10$)
  • $T_3 = 01101001$ (append complement of $0110$, which is $1001$)
• Recurrence Relation: The sequence satisfies the relations:
  • $t_{2n} = t_n$
  • $t_{2n+1} = 1 - t_n$

Fascinating Properties of the Sequence

Despite its simple definition, the Thue-Morse sequence possesses unique mathematical characteristics:

• Overlap-Free: It is "overlap-free", meaning it contains no subwords of the form $aXaXa$, where $a$ is a single symbol and $X$ is any word (empty or not). In other words, you will never see three consecutive identical blocks.
• Aperiodic: Although it is defined deterministically, it never becomes periodic. It is a classic example of an ordered but non-repeating sequence.
• Fractal Nature: If you plot the sequence as a series of left/right turns, it generates a beautiful self-similar fractal curve known as the Thue-Morse fractal.

How to Use the Thue-Morse Sequence Generator

Our online generator allows you to create terms of the sequence with extreme ease:

1. Enter the Number of Terms you want to generate (up to 10,000).
2. Customize the Symbols representing '0' and '1' to fit your formatting or puzzle needs.
3. Choose a Separator like a comma, space, semicolon, or new line, or select "None" for a continuous stream.
4. Toggle the Show Index Labels checkbox to display the exact index alongside each term.
5. Click Generate to instantly process the sequence. You can easily copy the output or download it as a text file.