Thue-Morse Sequence Generator

0110100110010110...

CalculatorsFreeNo Signup
4.5(78 reviews)
All Tools

Loading tool...

About Thue-Morse Sequence Generator

A Thue-Morse sequence generator producing t(n) = number of 1s in binary representation of n, mod 2. Equivalently: start 0, repeatedly append complement. Cube-free, self-similar, used for fair coin-toss compensation. Client-side.

Thue-Morse Sequence Generator Features

  • Sequence generation
  • Binary count
  • Self-similar
  • Cube-free proof
  • Fair division
Thue-Morse sequence: t(n) = popcount(n) mod 2. Start: 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0... Self-similar: append complement at each doubling. Cube-free (no XXX substring). Used for fair division: ABBABAAB... ensures equal treatment.

How to Use

Enter number of terms:

  • Sequence: Binary 0/1
  • Binary: Popcount method
  • Doubling: Complement rule

Fair Division

Picking teams: instead of ABABAB... (unfair: A always picks first), use Thue-Morse: ABBABAAB... This minimizes advantage. Used in chess (Thue-Morse tournament), penalty shootouts (proposed), and auction theory.

Properties

  • Cube-free: no XXX pattern (proved by Thue, 1906)
  • Self-similar under 01→0110, 10→1001
  • Uniform: equal 0s and 1s in the limit
  • Related to Sierpiński triangle (mod 2)

Step-by-Step Instructions

  1. 1Enter terms.
  2. 2View sequence.
  3. 3Check binary.
  4. 4See doubling.
  5. 5Explore fairness.

Thue-Morse Sequence Generator — Frequently Asked Questions

Why is it called 'cube-free'?+

No pattern of consecutive symbols repeats three times. You can never find XXX where X is any block of symbols. Thue proved this in 1906 — the first known cube-free sequence over 2 symbols. Over 3 symbols, square-free sequences exist.

How is it used for fair division?+

Instead of alternating ABABAB... (biased toward A), use Thue-Morse order: ABBABAAB... This 'balances' the advantage. After 2^n picks, both players have had equally favorable positions. Proposed for chess tournaments and penalty shootouts.

What's the connection to binary?+

t(n) = number of 1-bits in n, mod 2. So t(0)=0, t(1)=1, t(2)=1, t(3)=0 (3=11₂, two 1s), t(4)=1 (100₂, one 1). This makes computation O(1) per term. The sequence IS the parity of the binary digit sum.

More Calculators Tools

Explore all 639 other calculators tools available on Generatr

1-Sample Z-Test Calculator2-Sample Z-Test Calculator3D Surface Area CalculatorA/B Testing Significance CalculatorAbsolute Value CalculatorAbundant Number CheckerAccelerated Aging CalculatorAchromatic Number CalculatorAcyclic Chromatic Number CalculatorAdditive Persistence CalculatorAge CalculatorAging Test CalculatorAlbertson Index CalculatorAlgebraic Connectivity CalculatorAliquot Sequence CalculatorAliquot Sum CalculatorAlternating Series Test CalculatorAmicable Number FinderAnnuity CalculatorAPY CalculatorAquarium CO2 Drop CheckerArea CalculatorArea Under Curve CalculatorArithmetic Sequence CalculatorArmstrong Number CalculatorASCVD Risk CalculatorAspect Ratio CalculatorAtom Bond Connectivity CalculatorAugmented Eccentric Connectivity CalculatorAugmented Zagreb Index Calculator
View all 639 calculators tools
Share this tool: