Danger

This article is not yet released. If you’re seeing it, please note that it is not complete.

Prouhet-Thue-Morse Research 1: Foundations & Numeric Definitions

2026-04-13

This series is a hobby horse of mine. I have been working on it on-and-off since 2016, after seeing a Stand-up Maths video [Par] on the subject. I am in part adapting this from a more-academic version [AC] that I’ve never quite been able to finish. The problem I run into again and again is that I can only prove most of it, and that isn’t quite enough in the math world. I am putting this piece out there in part to look for a collaborator: someone who can help me finish this last mile. I will do my best to denote when a claim I make is proven by me, proven by others, or a conjecture. If it is conjecture, I will provide a level of confidence and some evidence for it.

This series is about the Prouhet-Thue-Morse Sequence [Inca]. In short: it is a fair-share sequence, a way to distribute value while giving the first mover as little advantage as possible. It is perfect for this use in two-player situations. In this series of blog posts, and eventually in a more formal paper, I hope to demonstrate the most logical ways to extend each definition, that those extensions are equivalent to each other, and that the resultant sequence does not preserve this property.

This series is divided into 8 entries. In entries 1, 2, and 3 we present each of the 21 definitions of the standard Prouhet-Thue-Morse Sequence as seen in the literature today, divided by category of definition. We first look at numeric methods, then operations on ordered collections of numbers. We next examine definitions that relate to other sequences of integers, followed by a pair of generating functions, a hypergeometric definition, one based on cellular automatons, and a derivation from Galois Duels.

In entry 4 we prove / postulate their equivalence with each other in the standard binary domain. In entry 5 we present 9 definitions that extend into larger domains. Most of these can only construct sequences with integer value elements, though a select few can be extended into even broader domains, such as rational bases. In entry 6 we prove / postulate that the extensions are equivalent to each other in the domain of positive integer bases. In entry 7 we examine the preservation (or failure) of properties for the standard Prouhet-Thue-Morse Sequence when extended to larger bases. Entry 8 is an appendix about honorable mention extensions and complexity analyses (both time and space) for the different definitions. These show which may be the most computationally efficient ways to calculate the Prouhet-Thue-Morse Sequence or Extended Prouhet-Thue-Morse Sequence, given your available resources.

Due to the complexity involved here, I’m not giving a timeline on any specific entry. They will come as they may, and I may end up adding to the series as progress arises.

1. Foundations & Binary Numeric Definitions (you are here)

2. Binary Definitions - Textual & Sequential

3. Binary Definitions - Others

4. Binary Equivalence

5. Extending the Alphabet

6. Extended Equivalence

7. Property Preservation

8. Complexity and Honorable Mentions

Introduction

It has often been said that the Prouhet-Thue-Morse Sequence is “taking turns taking turns taking turns…”. This is a useful way to think of it, and I want you to keep it in mind throughout this series. To me, the point of this sequence is about equitable distribution. If you have two players in any sort of game, and the value of a turn decreases over time. By “a game” here, I don’t just mean things like checkers or chess, but anything that can be phrased as a contest between two players. In other words, it can be generalized to any type of resource distribution.

What most interested me was the prospect of finding an extension of this sequence that would work for any number of players. To go about this, I began collecting different definitions of the sequence. For each of them, I would toy with ways to make it work for more than two players. A shocking number of them produced identical sequences, with some outliers that could use future investigation.

I want to start this series by going over the 2-player definitions and their distinguishing features. I think that by building an intuition for them, you will come to appreciate just how interesting this space is. In this entry we will be looking just at the numeric definitions, which are about one third of the total.

Notation

This entry requires us to define some notation. I want to do this at the beginning so that we don’t clutter the definitions below. In this entry, as well as future ones, I will introduce pieces of notation as the are most helpful. It will always appear at the top of an entry, and will always appear in the entry it is first meaningfully used in.

Notes and Admonitions

Throughout this series I will be making use of the admonitions feature to leave notes about possible leads, as well as marking conjectures and theorems. This lets me clearly communicate my level of confidence and indicate that this is a work in progress.

Conjecture 1.0

I will note conjectures like this. Each will come with an ID consisting of two parts: a series index and a count.

Theorem 1.0

Theorems will be identified like so, and given IDs similar to conjectures.

Lemma 1.0

Lemmas will also be written this way.

Hint

Possible leads to investigate will be marked as hints.

Specific to the Prouhet-Thue-Morse Sequence

When we refer to the Prouhet-Thue-Morse Sequence, we will always use it either as a name or as a function. If it is a name, we mean the sequence itself:

\[T = \left\langle0, 1, 1, 0, 1, 0, 0, 1, \dots\right\rangle\]

And when we refer to it as a function, what we mean is “this position in the sequence, starting with 0”:

\[T(n) = T_n\]

As a rule, when we refer to the Prouhet-Thue-Morse Sequence in equations, we will note that we mean the binary one like so:

\[T_2(3) = 0\]

When we are referring to a specific definition of the Prouhet-Thue-Morse Sequence, we will denote that with an additional subscript:

\[T_{2,1}(n) = f_1(n)\]

If we are referring to the Extended Prouhet-Thue-Morse Sequence, we will always note that as \(T_n\). In that form, the function receives an additional argument for what base we are working in:

\[\begin{split}\begin{aligned} T_{n}(x, s) &= \left(T_s\right)_x \\ T_{n}(x, 2) &= T_2(x) \end{aligned}\end{split}\]

And similarly, we will add a subscript whenever we are referring to a specific definition:

\[T_{n,1}(x) = f_1(x)\]

Exclusive Or

The only operation used in this entry that may not be familiar to our audience is the bitwise exclusive or, often shortened to XOR. We represent it with the symbol \(\oplus\), and it’s quite useful in programming. For non-negative integers, you can define it like so:

Lemma 1.1

\[x \oplus y = \displaystyle\hspace{-20pt}\sum_{i=0}^{\left\lfloor\log_2(\max(x, y))\right\rfloor} \hspace{-16pt} 2^i \cdot \left(\left\lfloor\dfrac{x}{2^i}\right\rfloor + \left\lfloor\dfrac{y}{2^i}\right\rfloor \hspace{-9pt} \mod{2}\right)\]

To verbalize that, it is checking if each bit in the binary representation of a number is different. If they are different, then that bit of the answer is 1. Otherwise it is 0.

We will also occasionally use it similarly to sigma notation, which looks like this:

Lemma 1.2

\[\displaystyle\bigoplus_{i=a}^b f(i) = f(a) \oplus f(a + 1) \oplus f(a + 2) \oplus \cdots \oplus f(b)\]

Binary Definitions - Numeric

As we discussed above, we’re going to be going over numeric definitions in this entry. What I mean by that is that they are defined by performing an operation purely on a single number, they are not referencing other sequences of integers, and they are not pulling in advanced math like generator functions or hypergeometry.

01 / 21 - Parity of Hamming Weight

This definition appears in [AS99, Inca, Pan, Spi20]. It is also the most common definition I see used.

The Hamming Weight, as typically defined, is the digit sum of a binary number. In other words, it is a count of the high bits in a given number. A common way to generate the Prouhet-Thue-Morse Sequence is to take the parity[1] of the Hamming Weight[2] for each natural number. We can define that as follows:

\[\begin{split}\begin{equation} \begin{aligned} p(0) &= 0 \\ p(n) &= (n \mod{2}) + p\left(\left\lfloor\dfrac{n}{2}\right\rfloor\right) \\ T_{2,1}(n) &= p(n) \mod{2} \end{aligned} \end{equation}\end{split}\]

This definition is incredibly easy to implement in a program. With some fairly standard Rust[3], you can write it using only a few operations for any type of number:

use num_traits::{One, Zero, one, zero};
use std::cmp::PartialOrd;
use std::ops::{BitAnd, ShrAssign};

fn ptms<I>(mut n: I) -> bool
where
    I: Copy + Zero + One + PartialOrd + ShrAssign + BitAnd<Output = I>,
{
    let mut answer: I = zero();
    while n > zero() {
        answer = (answer + n) & one();
        n >>= one();
    }
    return answer == one();
}

02 / 21 - Powers of Negative One

This appears in [Incb].

Another way to implement the modularity of the previous definition is to use the appropriate root of unity. In this paper, we use \(\omega_s = \exp\left(\tfrac{2i\pi}{s}\right)\) to represent the primitive root of unity in base \(s\), such that \((\omega_s)^s = 1\). Because of this, extracting the power of \((\omega_s)^x\) will give you the same value as \(x \mod{s}\).

There are two ways this can be approached. In the first we work with these output values directly, mapping \(\{1, -1\} \to \{0, 1\}\):

\[\begin{split}\begin{equation} \begin{aligned} T_{2,2}(n) &= \dfrac{1 - (\omega_2)^{p(n)}}{2} \\ &= \dfrac{1 - (-1)^{p(n)}}{2} \end{aligned} \end{equation}\end{split}\]

03 / 21 - Root of Unity

And in the second we extract the exponent:

\[\begin{split}\begin{equation} \begin{aligned} T_{2,3}(n) &= \dfrac{\log\left(\omega_2^{p(n)}\right)}{\log\left(\omega_2\right)} \\ &= \dfrac{\log\left((-1)^{p(n)}\right)}{\log(-1)} \\ &= \dfrac{(p(n) \mod{2}) \cdot \log(-1)}{\log(-1)} \\ &= \dfrac{(p(n) \mod{2}) \cdot i\pi}{i\pi} \\ &= p(n) \mod{2} \end{aligned} \end{equation}\end{split}\]

I believe this definition is unique to this series. While I admit that it’s a lot less efficient to calculate this way, as opposed to definition 2, but it allows for an extension later.

Because this is so trivial, I will include a proof of equivalence here.

Theorem 1.1

For all non-negative integers \(n\), \(T_{2,1}(n) = T_{2,3}(n)\)

\[\begin{split}\begin{equation} \begin{aligned} T_{2,1}(n) &= T_{2,3}(n) \\ p(n) \mod{2} &= \dfrac{\log\left(\omega_2^{p(n)}\right)}{\log\left(\omega_2\right)} \\ &= \dfrac{\log\left((-1)^{p(n)}\right)}{\log(-1)} \\ &= \dfrac{(p(n) \mod{2}) \cdot \log(-1)}{\log(-1)} \\ &= \dfrac{(p(n) \mod{2}) \cdot i\pi}{i\pi} \\ &= p(n) \mod{2} \end{aligned} \end{equation}\end{split}\]

04 / 21 - Recursion

This definition appears in [Inca, KAN91, Pan].

\[\begin{split}\begin{equation} \begin{aligned} T_{2,4}(0) &= 0 \\ T_{2,4}(2n) &= T_{2,4}(n) \\ T_{2,4}(2n+1) &= 1 - T_{2,4}(n) \end{aligned} \end{equation}\end{split}\]

05 / 21 - Floor-Ceiling Difference

This definition appears in [Inca].

Note

Some of the info that’s in the proof of equivalence should be lifted up into here

\[\begin{split}\begin{equation} \begin{aligned} b(n) &= \begin{cases} n &\text{if } n \le 1 \\ b\left(\left\lceil\dfrac{n}{2}\right\rceil\right) - b\left(\left\lfloor\dfrac{n}{2}\right\rfloor\right) &\text{otherwise} \end{cases} \\ T_{2,5}(n-1) &= \dfrac{1 - b(2n - 1)}{2} \pmod{2} \end{aligned} \end{equation}\end{split}\]

06 / 21 - Highest Bit Difference

This definition appears in [Arn10].

Hint

This seems very similar to the definition above, and I think that may be what this was derived from.

Note

The text below is from Wiki and needs to be entirely rewritten. I was able to derive the formula on my own from translating their code. This method leads to a fast method for computing the Prouhet-Thue-Morse Sequence: start with t0 = 0, and then, for each n, find the highest-order bit in the binary representation of n that is different from the same bit in the representation of n - 1. If this bit is at an even index, tn differs from tn - 1, and otherwise it is the same as tn - 1.

from itertools import count

def p2_d07():
   value = 1
   for n in count():
      # Assumes that (-1).bit_length() == 1
      x = (n ^ (n - 1)).bit_length() + 1
      if x & 1 == 0:
            # Bit index even, so toggle value
            value = 1 - value
      yield value

\[\begin{split}\begin{equation} \begin{aligned} T_{2,6}(0) &= 0 \\ T_{2,6}(n) &= \begin{aligned}[c] &\left\lfloor\log_2(n \oplus (n - 1))\right\rfloor \\ &+ T_{2,6}(n - 1) \pm 1 \end{aligned} \pmod{2} \end{aligned} \end{equation}\end{split}\]

07 / 21 - Hamming Weight Complement

This definition appears in [Incb]. The Hamming Weight Complement (defined as \(\overline{p}(n)\)) is the count of \(0\)s in the minimal binary representation of a number, and A054429 [Incc] is the sequence defined by reversing the order of integers between \(2^n\) and \(2^{n+1}-1\) (ex: \(0, 1, 3, 2, 7, 6, 5, 4, \dots\)).

\[\begin{split}\begin{equation} \begin{aligned} \text{A054429}(n) &= \begin{cases} 0 &\text{if } n = 0 \\ 3 \cdot 2^{\left\lfloor\log_2(n)\right\rfloor} - n - 1 &\text{otherwise} \end{cases} \\ \overline{p}(x) &= \left\lceil\log_2(x + 1)\right\rceil - p(x) \\ T_{2,7}(n) &= 1 - \overline{p}(\text{A054429}(n)) \mod{2} \end{aligned} \end{equation}\end{split}\]

Wrapping Up

Support

If you found this article useful, consider supporting my work. Reader support will help fund this writing, the research that goes into it, and open source development.

You can support this work on…

Footnotes

[1]

Whether a number is odd or even

[2]

The count of \(1\)s in the binary representation of a number

[3]

I know that the return statement is redundant, but I like explicitly having it

Citations

[AS99]

Jean-Paul Allouche and Jeffrey Shallit. The ubiquitous prouhet-thue-morse sequence. In C. Ding, T. Helleseth, and H. Niederreiter, editors, Sequences and their Applications, 1–16. London, 1999. Springer London.

[AC]

Olivia Appleton-Crocker. Thue-morse paper draft. URL: https://github.com/LivInTheLookingGlass/Thue-Morse/ (visited on 2026-03-02).

[Arn10]

Jorg Arndt. Matters computational. Springer, Berlin, Germany, oct 2010. ISBN 978-3-642-14763-7. doi:10.1007/978-3-642-14764-7.

[Inca] (1,2,3,4)

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A010060. The \TMS . URL: https://oeis.org/A010060 (visited on 2024-10-24).

[Incb] (1,2)

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A010059. The inversion of the \TMS . URL: https://oeis.org/A010059 (visited on 2024-10-24).

[Incc]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A054429. URL: https://oeis.org/A054429 (visited on 2024-10-24).

[KAN91]

M. Kolář, M. K. Ali, and Franco Nori. Generalized thue-morse chains and their physical properties. Phys. Rev. B, 43:1034–1047, Jan 1991. doi:10.1103/PhysRevB.43.1034.

[Pan] (1,2)

Diyath Pannipitiya. To symbolic dynamics through the thue-morse sequence. URL: https://arxiv.org/abs/2402.07015, arXiv:2402.07015.

[Par]

Matt Parker. The fairest sharing sequence ever. URL: https://www.youtube.com/watch?v=prh72BLNjIk.

[Spi20]

Lukas Spiegelhofer. The level of distribution of the thue–morse sequence. Compositio Mathematica, 156(12):2560–2587, 2020. doi:10.1112/S0010437X20007563.

Cite As

Click here to expand the bibtex entry.

@online{appleton_blog_0014,
  title    = { Prouhet-Thue-Morse Research 1: Foundations & Numeric Definitions },
  author   = { Olivia Appleton-Crocker },
  editor   = { Ultralee0 and Ruby },
  language = { English },
  version  = { 1 },
  date     = { 2026-04-13 },
  url      = { https://blog.oliviaappleton.com/posts/0014-thue-morse-01 }
}

Tags: math, hobby-horse

Comments ,