Danger

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

Prouhet-Thue-Morse Research 2: Binary Definitions - Textual & Sequential

2026-04-20

1. Foundations & Binary Numeric Definitions

2. Binary Definitions - Textual & Sequential (you are here)

3. Binary Definitions - Others

4. Binary Equivalence

5. Extending the Alphabet

6. Extended Equivalence

7. Property Preservation

8. Complexity and Honorable Mentions

Introduction

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.

Defining Strings

In this series, we will sometimes be looking at sequences of integers rather than specific integers. In those cases, we will refer to the general class of those as strings, and we will represent them using tuple notation. This should be fairly familiar for programmers. For example, the infinite string \(T_2\) is:

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

Strings can be finite or infinite, and are always referenced with their first “character” as 0. Strings can be concatenated together, and we will do so with the following notation:

\[\left\langle0, 1\right\rangle \mathbin{\|} \left\langle1, 0\right\rangle = \left\langle0, 1, 1, 0\right\rangle\]

This can also be represented in sigma notation, where the following operation lets us concatenate a sequence of strings:

\[\mathop{\mathbin{\Big\|}}_{i=0}^{9} \left\langle i \right\rangle = \left\langle 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \right\rangle\]

Binary Definitions - Textual

08 / 21 - Invert and Extend

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

This definition is more natural to think about as extending a tuple that contains the sequence. We will give a recurrence relation below, but to build an intuition we will work in this framework first. Let \(t_2(n)\) be the first $2^n$ elements of the Prouhet-Thue-Morse Sequence. Given this, we can define:

\[\begin{split}\begin{equation} \begin{aligned} \text{inv}(\mathbf{x}) &= \begin{cases} 0, &\text{if } x_i = 1 \\ 1, &\text{if } x_i = 0 \end{cases} \\ &\quad\quad\text{for } \mathbf{x} = \left\langle x_0, x_1, \ldots, x_{(|\mathbf{x}|-1)}\right\rangle \\ t_2(0) &= \left\langle 0 \right\rangle \\ t_2(n) &= t_2(n - 1) \mathbin{\|} \text{inv}(t_2(n - 1)) \end{aligned} \end{equation}\end{split}\]

Given the above, we can define a recurrence relation that will give us individual elements. It will be less efficient to compute, but will allow proofs of equivalence to be easier.

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

09 / 21 - Substitute and Flatten

This definition appears in [Inca, KAN91, Pan, Spi20]. It is one of the most commonly used because of its simplicity. Define the morphism \(\mu\) on the alphabet \(\{0, 1\}\) by \(\mu(0) = 01, \mu(1) = 10\). \(T_2\) is then the unique fixed point of \(\mu\) that begins with \(0\). In other words, \(T_2 = \lim_{n\to\infty}\mu^n(0)\).

\[\begin{split}\begin{equation} \begin{aligned} s(n) &= \begin{cases} \left\langle0, 1\right\rangle, &\text{if } n = 0 \\ \left\langle1, 0\right\rangle, &\text{if } n = 1 \end{cases} \\ t(0) &= \left\langle0\right\rangle \\ t(n) &= \mathop{\mathbin{\Big\|}}_{i=0}^{2^{n-1}-1} s(t(n-1)_i) \\ T_{2,9}(n) &= t(\left\lceil\log_2(n + 1)\right\rfloor)_n \end{aligned} \end{equation}\end{split}\]

So for example, calculating \(T_{2,9}(3)\) would look like:

\[\begin{split}\begin{equation} \begin{aligned} t(0) &= \left\langle0\right\rangle \\ t(1) &= \mathop{\mathbin{\Big\|}}_{i=0}^{0} s(t(0)_i) = \left\langle0, 1\right\rangle \\ t(2) &= \mathop{\mathbin{\Big\|}}_{i=0}^{1} s(t(1)_i) = \left\langle0, 1, 1, 0\right\rangle \\ T_{2,9}(3) &= t(\left\lceil\log_2(3 + 1)\right\rceil)_3 \\ &= t(2)_3 \\ &= \left\langle0, 1, 1, 0\right\rangle_3 \\ &= 0 \end{aligned} \end{equation}\end{split}\]

10 / 21 - Recursive Rotation

Another way to phrase the above definition is as recursive rotation. To the best of our knowledge, this definition is original to this project. If we decompose \(s\), we can instead represent it as:

\[\begin{split}\begin{equation} \begin{aligned} r(\mathbf{x}, i) &= \begin{aligned}[c] &\left\langle x_{0 + i \mod{|\mathbf{x}|}}, x_{1 + i \mod{|\mathbf{x}|}}, \ldots\right\rangle \\ &\text{for } \mathbf{x} = \left\langle x_0, x_1, \ldots, x_{(|\mathbf{x}|-1)}\right\rangle \end{aligned} \\ t(0) &= \left\langle0\right\rangle \\ t(1) &= \left\langle0, 1\right\rangle \\ t(n) &= \mathop{\mathbin{\Big\|}}_{i=0}^1 r\left(t(n-1), i \cdot 2^{n-2}\right) \\ T_{2,10}(n) &= t(\left\lceil\log_2(n + 1)\right\rceil)_n \end{aligned} \end{equation}\end{split}\]

Binary Definitions - Relation to Other Sequences

11 / 21 - Odious Numbers Derivation

This definition appears in [Inca].

Another way to generate the Prouhet-Thue-Morse Sequence is to take the sequence of Odious Numbers [Incc] mod \(2\). Odious numbers are those with an odd number of \(1\)s in their binary representation. Note that the player numbers in this derivation are swapped, so when generating this for testing and extension, we add 1 to the result. Some simple generating code [AC] for this is as follows:

from itertools import count

def p2_d11():
    for i in count():
        if i.bit_count() & 1:
            yield (i + 1) & 1

In mathematical terms, this can be translated to:

\[\begin{split}\begin{equation} \begin{aligned} no(n) &= \begin{cases} n &\text{if } p(n) \mod{2} = 1 \\ no(n+1) &\text{otherwise} \end{cases} \\ o(n) &= \begin{cases} 1 &\text{if }n = 0 \\ no(o(n-1) + 1) &\text{if } n > 0 \end{cases} \\ T_{2,11}(n) &= o(n) + 1 \pmod{2} \end{aligned} \end{equation}\end{split}\]

Hint

A possible way to extend this would be to reinterpret evenness as n-evenness.

Note

Aren’t Odious Numbers exactly the numbers where the parity of the hamming weight is 1? So doesn’t that mean that the Thue-Morse Sequence selects which numbers are Odious? From cursory testing, it seems to. There’s something to be had there.

Note

A related definition on OEIS [Inca] is

\[\begin{split}\begin{equation*} \begin{aligned} &T(n) + \text{Odious}(n - 1) + 1 = 2n \text{ for } n \ge 1 \\ &T(n) = 2n - \text{Odious}(n - 1) - 1 \end{aligned} \end{equation*}\end{split}\]

12 / 21 - Evil Numbers Derivation 1

This definition appears in [Inca].

Note

More text

The Evil Numbers [Incd] are those who have an even number of \(1\)s in their binary representation. Note that this is the opposite of the Odious Numbers referenced above.

from itertools import count

def evil():
    for i in count():
        if i.bit_count() & 1 == 0:
            yield i

def p2_d12():
    for n, i in enumerate(evil()):
        yield (i - 2 * n) & 1

In mathematical terms, this can be translated to:

\[\begin{split}\begin{equation} \begin{aligned} ne(n) &= \begin{cases} n &\text{if } p(n) \mod{2} = 1 \\ ne(n+1) &\text{otherwise} \end{cases} \\ e(n) &= \begin{cases} 1 &\text{if }n = 0 \\ ne(e(n-1) + 1) &\text{if } n > 0 \end{cases} \\ T_{2,12}(n) &= e(n) - 2n \pmod{2} \end{aligned} \end{equation}\end{split}\]

13 / 21 - Evil Numbers Derivation 2

This definition appears in [Incb].

Note

More text

A second, more-efficient derivation from the Evil Numbers is as follows, where \(ce()\) is the count of Evil Numbers less than \(n\) [Ince], and \(p()\) is the function defined in Definition 1 [].

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

14 / 21 - Odious & Evil Numbers Derivation

This definition appears in [Incb].

Note

More text as to why. Also, figure out why

A second, more-efficient derivation from the Evil Numbers is as follows, where \(ce()\) is the count of Evil Numbers less than \(n\) [Ince], and \(p()\) is the function defined in Definition 1 [].

\[\begin{split}\begin{equation} \begin{aligned} oe(n) &= \begin{cases} o\left(\left\lfloor\dfrac{n}{2}\right\rfloor\right) &\text{if } n \mod{2} = 0 \\ e\left(\left\lfloor\dfrac{n}{2}\right\rfloor\right) &\text{if } n \mod{2} = 1 \end{cases} \\ T_{2,14}(n) &= 1 - oe(n) \pmod{2} \end{aligned} \end{equation}\end{split}\]

15 / 21 - Gould’s Sequence Derivation

This definition appears in [Inca].

Gould’s Sequence [Incf] are the number of odd entries in a given row of Pascal’s Triangle. Note that of the numeric methods, this is the least computationally efficient definition in this paper (as you’ll see in the eighth entry of this series).

Note

Why mod 3? Everything else is mod 2. This definition is unlikely to be extendable, and the obvious routes fail. I don’t get why this works, and I think I need to. I think \(\text{Gould}(x)\) always returns \(2k + \{0,1\}\)

\[\begin{split}\begin{equation} \begin{aligned} T_{2,15}(n) &= \text{Gould}(n) - 1 \mod{3} \\ &= \left(\sum_{k=0}^n \left(\binom{n}{k} \mod{2} \right)\right) - 1 \mod{3} \end{aligned} \end{equation}\end{split}\]

16 / 21 - Blue Code Derivation

This definition appears in [Inca].

In the OEIS, this sequence [Incg] is defined as the “binary coding of a polynomial over GF(2), substitute x+1 for x”. There are a number of ways to generate it. One of the more computationally-accessible ones is:

\[\begin{split}\begin{equation} \begin{aligned} \text{A001317}(n) &= \sum_{k=0}^n \left(\binom{n}{k} \mod{2} \right) \cdot 2^k \\ f(n, i) &= \left\lfloor\dfrac{n}{2^i} \mod{2}\right\rfloor \\ \text{A193231}(n) &= \bigoplus_{i=0}^{\left\lceil\log_2(n)\right\rceil} \hspace{-5pt} (f(n, i) \cdot \text{A001317}(i \cdot f(n, i))) \\ T_{2,16}(n) &= \text{A193231}(n) \pmod{2} \end{aligned} \end{equation}\end{split}\]

Translated into words, this function computes the value of Sierpiński’s triangle for the index of each high bit, then takes the XOR of all such resulting values. Note that since \(f(n, i) = 0\) if and only if the \(i\)th bit of \(n\) is low, each low bit can be simplified out when calculating.

This definition is, frankly, absurd. No reasonable person would calculate the sequence this way. And yet, it works.

Hint

It seems to me that this might be extendable by using GF(n) instead of GF(2), though I don’t know of a way to efficiently compute or prove such a result

Citations

[AC]

Olivia Appleton-Crocker. Extending the thue-morse sequence source code. Available at: https://github.com/LivInTheLookingGlass/Thue-Morse, https://thue.oliviappleton.com. This repository contains the source code and data for the research presented in this paper.

[BORZ16]

Ethan D. Bolker, Carl Offner, Robert Richman, and Catalin Zara. The prouhet–tarry–escott problem and generalized thue–morse sequences. Journal of Combinatorics, 7(1):117–133, 2016. URL: http://dx.doi.org/10.4310/JOC.2016.v7.n1.a5, doi:10.4310/joc.2016.v7.n1.a5.

[Inca] (1,2,3,4,5,6,7)

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: A000069. The Odious Numbers. URL: https://oeis.org/A000069 (visited on 2024-10-24).

[Incd]

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

[Ince] (1,2)

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A159481. Number of evil numbers $\le n$. URL: https://oeis.org/A159481 (visited on 2024-10-24).

[Incf]

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

[Incg]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A193231. Blue code for n. URL: https://oeis.org/A193231 (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.

[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_0015,
  title    = { Prouhet-Thue-Morse Research 2: Binary Definitions - Textual },
  author   = { Olivia Appleton-Crocker },
  editor   = { Ultralee0 and Ruby },
  language = { English },
  version  = { 1 },
  date     = { 2026-04-20 },
  url      = { https://blog.oliviaappleton.com/posts/0015-thue-morse-02 }
}

Tags: math, hobby-horse

Comments ,