Danger

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

Prouhet-Thue-Morse Research 5: Extending the Alphabet¶

2026-05-04

Foundations & Binary Numeric Definitions
Binary Definitions - Textual & Sequential
Binary Definitions - Others
Binary Equivalence
Extending the Alphabet (you are here)
Extended Equivalence
Property Preservation
Complexity and Honorable Mentions

Introduction¶

While the Prouhet-Thue-Morse Sequence has a well-established binary form, its extension to larger alphabets introduces interpretive choices. In this work, we adopt a consistent methodology that extends all definitions equivalently. This approach ensures coherence across all extended definitions and preserves the underlying structure of the sequence. However, we acknowledge alternative constructions (such as the morphism $0\to012, 1\to02, 2\to1$ [Pan, Inca, Incb, Incc, Incd, Ince, Incf, Incg, Inch, Inci, Incj, Inck, Incl, Incm]) which deviate from these extensions. While these may yield sequences of interest, they do not align with the equivalence criteria established in our framework.

Extended Definitions - Numeric¶

1 / 9 - Modular Digit Sums¶

This definition appears in [Ast03, Dek23, Incn, Inco, Incp, Incq, Incr, Incs, Inct, Incu, Incv, McI, Par17, Rob, SSY, She, Sta].

To extend definition 1 from $2$ to $n$ players, we must first map our concept of parity to base $n$. We can do this by taking the parity equation defined above and replacing the $2$s with $n$, for $n \in \Integers_{\ge 2}$.

\[\begin{split}\begin{equation} \begin{aligned} p_n(0) &= 0 \\ p_n(x) &= x + p_n\left(\floor{\dfrac{x}{n}}\right) \pmod{n} \end{aligned} \end{equation}\end{split}\]

Under this definition, you can construct the Prouhet-Thue-Morse Sequence using the following, starting at 0:

\[\begin{equation} T_{n,1}(x, s) = p_s(x) \end{equation}\]

Note that this definition is trivially extensible to non-integer bases by redefining $p_n()$, though that is beyond the scope of this paper. This has been done in [Dek23, Incn]. It has also been extended to negative integer bases [Inco, SSY, She].

Some other works present a more generalized version, where

\[\begin{equation} t_{b,m}(n) = p_b(n) \mod{m} \end{equation}\]

This allows for increased flexibility, especially when using fractional bases. In this notation, for negative integer bases, $T_{n,1}(x, s) = p_s(x) \;\; \mod{|s|}$

Proof of Equivalence with Original Definition 1¶

\begin{proof}
\par\noindent\par
It is clear from visual inspection that $p_2$ is identical to our original definition of $p$.

\begin{equation}
    \begin{aligned}
                                                        p_2(x) &= p(x) \\
                        x + p_2\left(\floor{\dfrac{x}{2}}\right) &= x + p\left(\floor{\dfrac{x}{2}}\right) \\
x + \floor{\dfrac{x}{2}} + p_2\left(\floor{\dfrac{x}{2^2}}\right) &= x + \floor{\dfrac{x}{2}} + p\left(\floor{\dfrac{x}{2^2}}\right) \\
    x + \floor{\dfrac{x}{2}} + \floor{\dfrac{x}{2^2}} + \ldots &= x + \floor{\dfrac{x}{2}} + \floor{\dfrac{x}{2^2}} + \ldots
    \end{aligned}
\end{equation}
\end{proof}

This definition is also trivially extended to negative integer bases.

2 / 9 - Roots of Unity¶

\[\begin{equation} T_{n,2}(x,s) = \dfrac{\log\left(\omega_s^{p_s(x)}\right)}{\log\left(\omega_s\right)} \end{equation}\]

Proof of Equivalence with Original Definition 3¶

\begin{proof}
\par\noindent\par
    Let's start by substituting $s$ for $2$:
    \begin{equation}
    \begin{aligned}
T_{n,\arabic{extdefctr}}(x, 2) &= \dfrac{\log\left(\omega_2^{p_2(x)}\right)}{\log(\omega_2)} \\
                    &= \dfrac{\log\left((-1)^{p_2(x)}\right)}{\log(-1)} \\
                    &= \dfrac{(p_2(x) \mod{2}) \cdot \log(-1)}{\log(-1)} \\
                    &= \dfrac{(p_2(x) \mod{2}) \cdot i\pi}{i\pi} \\
                    &= p_2(x) \mod{2}
    \end{aligned}
    \end{equation}

    This is identical to $T_{2,1}$, which we earlier proved is equivalent to $T_{2,2}$.
\end{proof}

3 / 9 - Recursion¶

This definition is found in [Sch], which entered preprint around the time the original version of this was being drafted.

\[\begin{split}\begin{equation} \begin{aligned} T_{n,3}(0, s) &= 0 \\ T_{n,3}(s \cdot x, s) &= T_{n,3}(x, s) \\ T_{n,3}(s \cdot x + k, s) &= k + T_{n,3}(x, s) \pmod{s} \end{aligned} \end{equation}\end{split}\]

Proof of Equivalence with Original Definition 4¶

\begin{proof}
\par\noindent\par
    Let's begin by substituting $s$ for $2$:
\begin{equation}
\begin{aligned}
            T_{n,\arabic{extdefctr}}(0, 2) &= 0 \\
    T_{n,\arabic{extdefctr}}(2 \cdot x, 2) &= T_{n,\arabic{extdefctr}}(x, 2) \\
T_{n,\arabic{extdefctr}}(2 \cdot x + k, 2) &= k + T_{n,\arabic{extdefctr}}(x, 2) \pmod{2}
\end{aligned}
\end{equation}

Note that that only values for $k$ that fit in this definition are $0$ and $1$. This means we can further simplify to:
\begin{equation}
T_{n,\arabic{extdefctr}}(2 \cdot x + 1, 2) = 1 + T_{n,\arabic{extdefctr}}(x, 2) \pmod{2}
\end{equation}

This is very similar to the definition found in equation \ref{eq:p2_d4}, except that one is adding and the other subtracting. Fortunately, we know that the only values that $T_{2,4}$ will return are $0$ and $1$, which means that these operations will be completely equivalent.

\begin{align*}
1 - 0 \mod{2} &= 1 + 0 \mod{2} \\
1 - 1 \mod{2} &= 1 + 1 \mod{2}
\end{align*}
\end{proof}

4 / 9 - Highest Digit Difference¶

\[\begin{split}\begin{equation} \begin{aligned} \text{XOR}_{n}(a, b) &= \hspace{-13pt} \sum_{i=0}^{\ceil{\log_{n}(\max(a,b) + 1)}} \hspace{-15pt} n^i \left(\floor{\dfrac{a}{n^i}} - \floor{\dfrac{b}{n^i}} \mod{n}\right) \\ T_{n,5}(0, s) &= 0 \\ T_{n,5}(x, s) &= \begin{aligned}[c] &\floor{\log_s(\text{XOR}_{s}(x, x - 1))} \\ &+ T_{n,4}(x - 1, s) + 1 \end{aligned} \pmod{s} \end{aligned} \end{equation}\end{split}\]

Note

Substitute n for 2, then simplify, plus a bit

Proof of Equivalence with Original Definition 6¶

5 / 9 - Increment and Extend¶

Note

[CK] gives a good example on how to possibly adapt inversion to incrementing

In the original version of this definition, we inverted the elements. In base $2$, this is the same thing as adding 1 (mod 2). Given that, let $t(x, n)$ be the first $n^x$ elements of the Extended Prouhet-Thue-Morse Sequence, for $n \in \Integers_{\ge 2}$.

\[ \begin{align}\begin{aligned}\begin{split}\begin{equation} \text{inc}(\mathbf{x}, n) = \begin{aligned}[c] &x_i + 1 \pmod{n} \\ &\text{for } \mathbf{x} = (x_0, x_1, \ldots, x_{(|\mathbf{x}|-1)}) \end{aligned} \end{equation}\end{split}\\\begin{split}\begin{equation} \begin{aligned} t(0, n) &= \tuple{0} \\ t(1, n) &= \tuple{0, 1, \ldots, n - 1} \\ t(x, n) &= t(x - 1, n) \cdot \text{inc}(t(x - 1, n), n) \end{aligned} \end{equation}\end{split}\end{aligned}\end{align} \]

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_{n,5}(0, s) &= 0 \\ T_{n,5}(x, s) &= T_{n,5}\left(x - s^{\floor{\log_s(x)}}, s\right) + 1 \pmod{s} \end{aligned} \end{equation}\end{split}\]

Proof of Equivalence with Original Definition 8¶

6 / 9 - Substitute and Flatten¶

This definition appears in [Brl89, CW19, Incp, Incq]

Note

There’s a bit of a leap here, since we have to explain why the rotation is equivalent to the binary choice presented in the original. There also might be a better syntax to define the rotation, perhaps using the format used in inv and inc.

\[\begin{split}\begin{equation} \begin{aligned} b(s) &= \tuple{0, 1, \cdots, s - 2, s - 1} \\ r(\mathbf{x}, i) &= \begin{aligned}[c] &\tuple{x_{0 + i \mod{|\mathbf{x}|}}, x_{1 + i \mod{|\mathbf{x}|}}, \ldots} \\ &\text{for } \mathbf{x} = \tuple{x_0, x_1, \ldots, x_{(|\mathbf{x}|-1)}} \end{aligned} \\ s(x, s) &= r(b(s), x) \\ t(0) &= \tuple{0} \\ t(x, s) &= \bigparallel_{i=0}^{2^{x-1}-1} s(t(x-1)_i, s) \\ T_{n,6}(x, s) &= t(\ceil{\log_s(x + 1)}, s)_x \end{aligned} \end{equation}\end{split}\]

Proof of Equivalence with Original Definition 9¶

7 / 9 - Recursive Rotation¶

\[\begin{split}\begin{equation} \begin{aligned} r(\mathbf{x}, i) &= \begin{aligned}[c] &\tuple{x_{0 + i \mod{|\mathbf{x}|}}, x_{1 + i \mod{|\mathbf{x}|}}, \ldots} \\ &\text{for } \mathbf{x} = \tuple{x_0, x_1, \ldots, x_{(|\mathbf{x}|-1)}} \end{aligned} \\ t(0, s) &= \tuple{0} \\ t(1, s) &= \tuple{0, 1, \ldots, s - 1} \\ t(x, s) &= \bigparallel_{i=0}^{s-1} r\left(t(x-1, s), i \cdot s^{x-2}\right) \\ T_{n,7}(x, s) &= t(\ceil{\log_s(x + 1)}, s)_x \end{aligned} \end{equation}\end{split}\]

Proof of Equivalence with Original Definition 10¶

8 / 9 - Latin Square Constructions¶

This definition appears in [BORZ16, Tom]

Let $L(n)$ be the reduced-form Latin Square with a first row of $\tuple{0, 1, \dots, n\!-\!1}$, and where each row progresses from one entry to the next as $L(n)_{a,x+1} \equiv L(n)_{a,x} + 1 \pmod{n}$. For each iteration $t_n$, substitute each entry $x$ for the string $L(n)_{x,*}$.

\note{Needs more explanation, largely copying from std def 8}

\begin{equation}
L(N) = \begin{pmatrix}
0 & 1 & 2 & \dots & N\!\!-\!\!1 \\
1 & 2 & \ddots & N\!\!-\!\!1 & 0 \\
2 & \ddots & N\!\!-\!\!1 & 0 & 1 \\
\vdots & N\!\!-\!\!1 & 0 & 1 & \ddots \\
N\!\!-\!\!1& 0 & 1 & \ddots & \ddots
\end{pmatrix}
\end{equation}

Proof of Equivalence with Original Definition 9¶

9 / 9 - Generating Functions¶

\[\begin{split}\begin{equation} \begin{aligned} G_s(x) &= \mathcal{G.F.} \;\; \begin{aligned} \prod_{k\ge0}^\infty \sum_{i=0}^{s-1} \omega_s^i \cdot x^{i \cdot s^k} \end{aligned} \\ \omega_s ^{T_{n,9}(j, s)} &= [x^j]G_s(x) \\ T_{n,9}(j, s) &= \dfrac{\log\left([x^j]G_s(x)\right)}{\log(\omega_s)} \\ &= \dfrac{\log\left([x^j]G_x(x)\right) \cdot s}{2i\pi} \\ \end{aligned} \end{equation}\end{split}\]

A similar definition to the below is found in [BZ] for $x \in \mathbf{Q}((x^{-1}))$. While that definition is equivalent to $T_2$, it does not match the values for the other generalizations in this paper. For a specific example:

\[\begin{split}\begin{equation} \begin{aligned} T_3 &= \tuple{0,1,2,1,2,0,2,0,1,\ldots} \\ T'_3 &= \tuple{0,2,0,2,1,0,0,0,0,\ldots} \pmod{3} \end{aligned} \end{equation}\end{split}\]

Note

Above needs checking. I am only 80% confident in my analysis here.

Proof of Equivalence with Original Definition 17¶

\begin{proof}
\par\noindent\par
\textbf{Observation 1}: to start, let us rephrase definition 17 slightly

\begin{equation}
\begin{aligned}
T_{2,17}(n) &= [x^n]G(x) \\
    &= [x^n] \left(\begin{aligned}[c]
    \dfrac{\displaystyle\sum_{k\ge0}^\infty x^k - \prod_{k \ge 0}^\infty (1 - x^{2^k})}{2}
    \end{aligned}\right) \\
    &= \dfrac{[x^n] \left(\begin{aligned}[c]
    \displaystyle\sum_{k\ge0}^\infty x^k - \prod_{k \ge 0}^\infty (1 - x^{2^k})\end{aligned}\right)}{2}
    \\
    &= \dfrac{1 - [x^n]\begin{aligned}[c]
    \displaystyle\prod_{k \ge 0}^\infty (1 - x^{2^k})
    \end{aligned}
    }{2}
\end{aligned}
\end{equation}

\textbf{Observation 2}: the aparatus around the infinite product exists entirely to translate $\{1, -1\} \to \{0, 1\}$. Another way to do that is to take the complex log of this output: for $x = \{1, -1\}: \tfrac{\log(x)}{\log(-1)} = \{0, 1\}$

\textbf{Inference 1}: \begin{equation}
    \dfrac{1 - [x^n]\begin{aligned}
    \displaystyle\prod_{k \ge 0}^\infty (1 - x^{2^k})
    \end{aligned}
    }{2} = \dfrac{\log\left([x^n]\begin{aligned}
    \displaystyle\prod_{k \ge 0}^\infty (1 - x^{2^k})
    \end{aligned}\right)}{\log(-1)}
\end{equation}

\textbf{Observation 3}: $\omega_2 = -1$

\textbf{Observation 4}: If we take $T_{n,\arabic{extdefctr}}(x, s)$ for $s=2$, we get \begin{equation}
\begin{aligned}
    G_2(x) &= \mathcal{G.F.} \;\; \begin{aligned}
    \prod_{k\ge0}^\infty \sum_{i=0}^{2-1} \omega_2^i \cdot x^{i \cdot 2^k}
    \end{aligned} \\
        &= \mathcal{G.F.} \;\; \begin{aligned}
    \prod_{k\ge0}^\infty \omega_2^0 \cdot x^{0 \cdot 2^k} + \omega_2^i \cdot x^{i \cdot 2^k}
    \end{aligned} \\
        &= \mathcal{G.F.} \;\; \begin{aligned}
    \prod_{k\ge0}^\infty 1 + (-1) \cdot x^{2^k}
    \end{aligned} \\
        &= \mathcal{G.F.} \;\; \begin{aligned}
    \prod_{k\ge0}^\infty 1 - x^{2^k}
    \end{aligned}
\end{aligned}
\end{equation}
This is identical to the product found in $T_{2,17}$.

\textbf{Conclusion}: $T_{n,\arabic{extdefctr}}(x, s) = T_{2,17}(x)$
\end{proof}

Citations

[Ast03]

Ricardo Astudillo. On a class of thue-morse type sequences. Journal of Integer Sequences, 2003.

[BZ]

Dzmitry Badziahin and Evgeny Zorin. On generalized thue-morse functions and their values. URL: https://arxiv.org/abs/1509.00297, arXiv:1509.00297.

[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.

[Brl89]

Srećko Brlek. Enumeration of factors in the thue-morse word. Discrete Applied Mathematics, 24(1):83–96, 1989. URL: https://www.sciencedirect.com/science/article/pii/0166218X9290274E, doi:https://doi.org/10.1016/0166-218X(92)90274-E.

[CK]

Yi Cai and Vilmos Komornik. Difference of cantor sets and frequencies in thue–morse type sequences. URL: https://arxiv.org/abs/2006.16119, arXiv:2006.16119.

[CW19]

Jin Chen and Zhi-Xiong Wen. On the abelian complexity of generalized thue-morse sequences. Theoretical Computer Science, 780:66–73, aug 2019. URL: http://dx.doi.org/10.1016/j.tcs.2019.02.014, doi:10.1016/j.tcs.2019.02.014.

[Dek23] (1,2)

F. M. Dekking. The thue-morse sequence in base 3/2. Journal of Integer Sequences, 2023.

[Inca]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A036577. Ternary Thue-Morse sequence: closed under $a \to abc, b \to ac, c \to b$. URL: https://oeis.org/A036577 (visited on 2024-10-24).

[Incb]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A007413. A squarefree (or Thue-Morse) ternary sequence: closed under $1\to 123, 2\to 13, 3\to 2$. Start with 1. URL: https://oeis.org/A007413 (visited on 2024-10-24).

[Incc]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A036585. Ternary Thue-Morse sequence: closed under $a \to abc, b \to ac, c \to b$. URL: https://oeis.org/A036585 (visited on 2024-10-24).

[Incd]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A036580. Ternary Thue-Morse sequence: closed under $a \to abc, b \to ac, c \to b$. URL: https://oeis.org/A036580 (visited on 2024-10-24).

[Ince]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A005679. Ternary Thue-Morse sequence: closed under $a \to abc, b \to ac, c \to b$. URL: https://oeis.org/A005679 (visited on 2024-10-24).

[Incf]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A036581. Ternary Thue-Morse sequence: closed under $a \to abc, b \to ac, c \to b$. URL: https://oeis.org/A036581 (visited on 2024-10-24).

[Incg]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A036582. Ternary Thue-Morse sequence: closed under $a \to abc, b \to ac, c \to b$. URL: https://oeis.org/A036582 (visited on 2024-10-24).

[Inch]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A036584. Ternary Thue-Morse sequence: closed under $a \to abc, b \to ac, c \to b$. URL: https://oeis.org/A036584 (visited on 2024-10-24).

[Inci]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A036579. Ternary Thue-Morse sequence: closed under $a \to abc, b \to ac, c \to b$. URL: https://oeis.org/A036579 (visited on 2024-10-24).

[Incj]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A036583. Ternary Thue-Morse sequence: closed under $a \to abc, b \to ac, c \to b$. URL: https://oeis.org/A036583 (visited on 2024-10-24).

[Inck]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A036586. Ternary Thue-Morse sequence: closed under $a \to abc, b \to ac, c \to b$. URL: https://oeis.org/A036586 (visited on 2024-10-24).

[Incl]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A036578. Ternary Thue-Morse sequence: closed under $a \to abc, b \to ac, c \to b$. URL: https://oeis.org/A036578 (visited on 2024-10-24).

[Incm]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A029883. First differences of the Thue-Morse sequence (A001285). URL: https://oeis.org/A029883 (visited on 2024-10-24).

[Incn] (1,2)

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A357448. The \ETMS in Base 3/2. URL: https://oeis.org/A357448 (visited on 2024-10-24).

[Inco] (1,2)

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A269027. The \ETMS in base -2. URL: https://oeis.org/A269027 (visited on 2024-10-24).

[Incp] (1,2)

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A053838. The \ETMS in Base 3, A.K.A sum of digits of n written in base 3 modulo 3. URL: https://oeis.org/A053838 (visited on 2024-10-24).

[Incq] (1,2)

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A053839. The \ETMS in Base 4, A.K.A sum of digits of n written in base 4 modulo 4. URL: https://oeis.org/A053839 (visited on 2024-10-24).

[Incr]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A053840. The \ETMS in Base 5, A.K.A sum of digits of n written in base 5 modulo 5. URL: https://oeis.org/A053840 (visited on 2024-10-24).

[Incs]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A053841. The \ETMS in Base 6, A.K.A sum of digits of n written in base 6 modulo 6. URL: https://oeis.org/A053841 (visited on 2024-10-24).

[Inct]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A053842. The \ETMS in Base 7, A.K.A sum of digits of n written in base 7 modulo 7. URL: https://oeis.org/A053842 (visited on 2024-10-24).

[Incu]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A053843. The \ETMS in Base 8, A.K.A sum of digits of n written in base 8 modulo 8. URL: https://oeis.org/A053843 (visited on 2024-10-24).

[Incv]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A053844. The \ETMS in Base 9, A.K.A sum of digits of n written in base 9 modulo 9. URL: https://oeis.org/A053844 (visited on 2024-10-24).

[McI]

Matt McIrvin. Fractions, fractals and thue-morse sequences. A 3 part series of blog posts: 1) https://mmcirvin.dreamwidth.org/499645.html, 2) https://mmcirvin.dreamwidth.org/499830.html, 3) https://mmcirvin.dreamwidth.org/500104.html.

[Pan]

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

[Par17]

Olga G. Parshina. On Arithmetic Index in the Generalized Thue-Morse Word, pages 121–131. Springer International Publishing, 2017. URL: http://dx.doi.org/10.1007/978-3-319-66396-8_12, doi:10.1007/978-3-319-66396-8_12.

[Rob]

Gerardo González Robert. Generalized thue-morse continued fractions. URL: https://arxiv.org/abs/1302.1900, arXiv:1302.1900.

[Sch]

Leif Schaumann. Generalized results on the convergence of thue-morse turtle curves. URL: https://arxiv.org/abs/2412.06183, arXiv:2412.06183.

[SSY] (1,2)

Jeffrey Shallit, Sonja Linghui Shan, and Kai Hsiang Yang. Automatic sequences in negative bases and proofs of some conjectures of shevelev. URL: https://arxiv.org/abs/2208.06025, arXiv:2208.06025.

[She] (1,2)

Vladimir Shevelev. Two analogs of thue-morse sequence. URL: https://arxiv.org/abs/1603.04434, arXiv:1603.04434.

[Sta]

Štěpán Starosta. Generalized thue-morse words and palindromic richness. URL: https://arxiv.org/abs/1104.2476, arXiv:1104.2476.

[Tom]

C. Robinson Tompkins. Latin square thue-morse sequences are overlap-free. URL: https://arxiv.org/abs/0706.0907, arXiv:0706.0907.

Cite As

Click here to expand the bibtex entry.

@online{appleton_blog_0017,
  title    = { Prouhet-Thue-Morse Research 5: Extending the Alphabet },
  author   = { Olivia Appleton-Crocker },
  editor   = { Ultralee0 and Ruby },
  language = { English },
  version  = { 1 },
  date     = { 2026-05-11 },
  url      = { https://blog.oliviaappleton.com/posts/0018-thue-morse-05 }
}

Tags: math, hobby-horse

Prouhet-Thue-Morse Research 5: Extending the Alphabet¶

Introduction¶

Extended Definitions - Numeric¶

1 / 9 - Modular Digit Sums¶

Proof of Equivalence with Original Definition 1¶

2 / 9 - Roots of Unity¶

Proof of Equivalence with Original Definition 3¶

3 / 9 - Recursion¶

Proof of Equivalence with Original Definition 4¶

4 / 9 - Highest Digit Difference¶

Proof of Equivalence with Original Definition 6¶

5 / 9 - Increment and Extend¶

Proof of Equivalence with Original Definition 8¶

6 / 9 - Substitute and Flatten¶

Proof of Equivalence with Original Definition 9¶

7 / 9 - Recursive Rotation¶

Proof of Equivalence with Original Definition 10¶

8 / 9 - Latin Square Constructions¶

Proof of Equivalence with Original Definition 9¶

9 / 9 - Generating Functions¶

Proof of Equivalence with Original Definition 17¶

Comments ,