How is each term of the Thue-Morse sequence computed?

Term n is 0 if the number of 1 bits in n's binary representation is even, and 1 if it's odd. For example, 6 in binary is 110, which has two 1 bits, an even count, so the term at index 6 is 0.

Why is this sequence called "Prouhet-Thue-Morse"?

It's named for three mathematicians who independently discovered or applied it: Eugène Prouhet in the 1850s in connection with a number theory problem, Axel Thue around 1906 in his work on combinatorics on words, and Marston Morse in the 1920s in dynamical systems research.

What is the sequence useful for beyond pure math?

It's famous as a square-free sequence, meaning it contains no substring immediately repeated back-to-back, and it has practical applications in fair division problems, chess (the Prouhet-Thue-Morse sequence appears in discussions of infinite chess move sequences avoiding repetition), and even in certain audio and coding theory contexts.

How many terms can I generate?

Up to 10,000. Each term is computed independently from its index's binary digit sum, so generation is fast even at the upper limit.

Thue-Morse Sequence Generator - Binary Digit Sum Parity

Overview

Introduction

The Prouhet-Thue-Morse sequence is one of the most studied automatic sequences in mathematics, notable for its independent discovery across three different eras and fields, number theory, combinatorics on words, and dynamical systems.

This generator computes any requested number of terms directly from each index's binary representation, following the sequence's simple parity-of-1-bits rule.

What Is Generate Prouhet-Thue-Morse Sequence?

The Prouhet-Thue-Morse sequence, cataloged as OEIS A010060, is a binary sequence where the term at index n depends only on the parity of the count of 1 bits in n's binary representation.

It begins 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ..., and is famous for being square-free, meaning no block of consecutive terms is immediately repeated, a property with deep connections to combinatorics on words.

How Generate Prouhet-Thue-Morse Sequence Works

For each index n starting at 0, the tool converts n to its binary representation by repeatedly checking its lowest bit and shifting right, counting how many of those bits are 1.

If that count of 1 bits is even, the term is 0, if odd, the term is 1, this parity check, sometimes called the "digit sum modulo 2", is applied independently to every index to build the full sequence.

When To Use Generate Prouhet-Thue-Morse Sequence

Use it when studying automatic sequences, square-free words, or the sequence's applications in fair-division algorithms and combinatorial game theory.

It's also a useful companion to Paperfolding Sequence Generator and Rudin-Shapiro Sequence Generator, two other classic automatic sequences over the same {0, 1} alphabet with very different defining rules.

Often used alongside Generate Paperfolding Sequence, Generate Rudin-Shapiro Sequence and Generate Baum-Sweet Sequence.

Features

Advantages

Computes each term independently and exactly from its index's bit pattern, with no cumulative error or drift over long runs.
Matches the canonical OEIS A010060 sequence precisely, useful as a verified reference for testing other implementations.
Handles large term counts efficiently since bit-counting for each index is a fast, constant-time-per-bit operation.

Limitations

Capped at 10,000 terms, chosen to keep the output a manageable size to read, copy, or pass into a chained tool.
Outputs only the raw 0/1 sequence; it doesn't compute derived properties like the sequence's square-free substring analysis or its fair-division applications directly.

Examples

First 16 terms of the Thue-Morse sequence

Input

Output

0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0

Index 3 is binary 11, two 1 bits (even), giving term 0; index 5 is binary 101, two 1 bits (even), also giving term 0; index 7 is binary 111, three 1 bits (odd), giving term 1.

Best Practices & Notes

Best Practices

Generate at least 8 terms if you want to visually confirm the sequence's self-similar block structure, where each doubling of length mirrors and complements the prior block.
Use a larger term count when studying the sequence's square-free property, since spotting the absence of immediate repeats is clearer over a longer run.

Developer Notes

The parity check uses a simple bit-counting loop, `while (x > 0) { ones += x & 1; x >>>= 1; }`, then returns `ones % 2`, an O(log n) per-term operation that scales cleanly up to the 10,000-term cap without any measurable slowdown.

Generate Prouhet-Thue-Morse Sequence Use Cases

Studying automatic sequences, square-free words, and combinatorics on words
Exploring fair-division algorithms and combinatorial game theory applications that reference the Thue-Morse sequence
Generating verified reference terms to test a custom binary digit-sum-parity implementation

Common Mistakes

Confusing this with the Rudin-Shapiro sequence, both are automatic sequences derived from binary representations, but Rudin-Shapiro counts adjacent "11" bit pairs rather than total 1 bits.
Assuming the sequence repeats periodically, it never does, its defining square-free property guarantees no block of terms is ever immediately repeated.

Tips

Try computing a few terms by hand from their binary form to build intuition before trusting a longer generated run.
Compare this sequence's self-similar doubling structure against Paperfolding Sequence Generator's output to see two very differently defined automatic sequences over the same two-symbol alphabet.

Generate Prouhet-Thue-Morse Sequence