How to Generalize the Thue-Morse Sequence to More Than Two Symbols?

combinatoricssequences-and-series

The Thue-Morse sequence is defined as a binary sequence and can be generated like

  0, 01, 01 10, 01 10 10 01, 01 10 10 01 10 01 01 10, ... .

So the second half of the series is always the binary complement of the first half of the series.

But is there a way to generate an analogous ternary sequence?
Intuitively my first guess for a ternary Thue-Morse sequence was like

  0, 01, 012, 012 120, 012 120 120 201, 012 120 120 201 120 201 201 012, ...

So here the second half of the series is the "ternary complement" (rotation $0 \to 1, 1 \to 2, 2 \to 0 $ instead of $0 \to 1, 1 \to 0 $) of the first half.

But it could also be

  0, 01, 012, 012 120 201, 012 120 201 120 201 012 201 012 120, ...

Here the second third is the "ternary complement" of the first third and the third third is the "ternary complement" of the second third.

Does any of my constructions for a ternary Thue-Morse series make sense?
Is there maybe a unique way to generate an analogous ternary sequence?
And how to construct n-ary versions of the Thue-Morse series in general?

Best Answer

It's $0, 012, 012 120 201, 012 120 201 120 201 012 201 012 120, ...$

To easily construct the Thue-Morse sequence, you can do the following:

Start with $0$; Replace $(0\to01)$ and $(1\to10)$. So you get: $$0, 0 1, 01 10, 0110 1001, 01101001 10010110,...$$

To easily construct the ternary version of Thue-Morse sequence, you can do the following:

Start with $0$; Replace $(0\to012), (1\to120), (2\to201).$ So you get: $$0, 0 1 2, 012 120 201, 012120201 120201012 201012120$$

To easily construct the $4$-ary version of Thue-Morse sequence, you can do the following:

Start with $0$; Replace $(0\to 0123), (1\to 1230), (2\to2301), (3\to3012).$ So you get: $$0, 0 1 2 3, 0123 1230 2301 3012, 0123123023013012 1230230130120123 2301301201231230 3012012312302301$$

To easily construct the $n$-ary version of Thue-Morse sequence, you can do the following:

Start with $0$; Replace

$$(0\to012\cdots[n-2][n-1]n), (1\to123\cdots[n-1]n0),$$

$$(2\to234\cdots n01),$$

$$\dots$$

$$(n\to n01\cdots[n-3][n-2][n-1]).$$

Related Solutions

[Math] Does this sequence have any mathematical significance

If I use abc to generate the sequence it comes out like this:

abc                       3
bc                        5
c bc                      8
c c bc                    12
bc c c bc                 18
c bc bc c c bc            27
c c c bc c bc bc c c bc   41

The list of numbers on the right, the sequence length up to that point, is A061419. A Mills-type formula for this sequence has the constant $\frac{2}{3}K(3)$, where $K(3)$ is A083286, and this last constant is related to the Josephus problem.

So your sequence is related to prime number sieves and the prime number theorem, which are closely linked with the Josephus problem. That you could not find the sequence in the OEIS is most likely because mathematics in this area lags behind other fields of number theory.

[Math] What’s the fairest turn sequence for n players

I have found an answer in the shape of an essentially brute-force Python 3 program I threw together. I will not accept my own answer because I'm hoping there are better takes on this, like a proper recursion or Lindenmayer system to quickly construct this solution. I am not entirely sure at this point, whether the resulting sequence generalizes Thue-Morse in all possible ways regarding "turn order fairness" but it at least does in one particular way:

Say there are two players taking turns, each trying to be the first to score a point throwing basketballs through hoops.
Both players have a low probability $\epsilon \approx 0$ of making the shot.
Conversely, they have a chance of $1-\epsilon$ to miss.
Acknowledging that a naive alternating turn order gives an unfair advantage to player 1, they decide on the following policy:
Whoever currently is the "underdog", that is, they have a lower probability of winning the game, goes next.
This, it turns out, gives the Thue-Morse-sequence of turns in the limit $\epsilon \to 0$.

Here is how it works:

The two players assign who may go first with a random coin flip. That person will be called player $A$, the other one player $B$. The current probability score for each player can be kept track of in a pair $(p_1, p_2)$. So after the first throw the score looks like this: $(\epsilon, 0)$.
Player $B$ has now become the underdog and gets the next turn. Since the game might already have ended, their winning probability is slightly lower though: $\left(\epsilon, \epsilon\left(1-\epsilon\right)\right) = \left(\epsilon, \epsilon-\epsilon^2\right)$
So at this point they still are the underdog and get to throw again: $\left(\epsilon, \epsilon\left(1-\epsilon+\left(1-\epsilon\right)^2\right)\right) = \left(\epsilon, 2\epsilon - 3\epsilon^2 + \epsilon^3\right)$.
At this point, since $\epsilon \approx 0$, $2\epsilon-3\epsilon^2$ will definitely be larger than $\epsilon$, so the next turn goes to player $A$ again. The turn order thus far was $A, B, B, A$ and if you keep following this process, you will generate the entire Thue-Morse sequence. (The referenced paper, however, mentions this other paper to construct a strictly fairer sequence. If I read it right, that sequence can't be easily constructed though. Unless somebody has further insight into this, I will stick with Thue-Morse for now.)

Here is the same algorithm now applied to three players. Initially, nobody has taken a turn. Since the turn order is determined by linear combinations of $(1-\epsilon)^n$ after $n$ turns, the matrix you see simply contains the (positive) integer coefficients if you expand the corresponding turn value. The top row denotes whether the column counts positively or negatively. We are always looking for the currently most disadvantaged player, so we are looking, from left to right, which player has the lowest winning probability. (Note, since I pulled out the sign to the top of the table, for negative columns we are looking for the maximum instead. Or just keep in mind that those values have a $-$ in front, then we are always minimizing.)

$$ \begin{matrix} & + \\ A & \mathbf{0} \\ B & 0 \\ C & 0 \end{matrix} $$

In a patt situation (As far as I could tell this only ever happens at the very beginning, but a proof of that would be nice), I give the first player the move. Below the matrix you can see the current sequence:

$$ \begin{matrix} & + \\ A & 1 \\ B & \mathbf{0} \\ C & 0 \end{matrix} \\ a $$

Higher turns require more columns for keeping track of everything:

$$ \begin{matrix} & + & - \\ A & 1 & 0 \\ B & 1 & 1 \\ C & \mathbf{0} & 0 \end{matrix} \\ ab $$

Let's jump ahead a little , to turn 6. The fat element denotes which element determines the next turn's player:

$$ \begin{matrix} & + & - & + & - & + & -\\ A & 2 & 5 & 10 & 10 & 5 & 1 \\ B & 2 & 5 & 6 & 4 & 1 & 0 \\ C & 2 & 5 & \mathbf{4} & 1 & 0 & 0 \end{matrix} \\ abccba $$

So the next turn goes to player $C$. Since they just got to play, this player now gets penalized with a term $(1-\epsilon)^6$ which will have coefficients according to $(-1)^k \begin{pmatrix} 6 \\ k \end{pmatrix}$, where $\begin{pmatrix} n \\ k \end{pmatrix}$ is the binomial coefficient, so, after adding another column to make room for all of the values, the following will be added to $C$'s row: $\begin{pmatrix}1 & 6 & 15 & 20 & 15 & 6 & 1\end{pmatrix}$, so:

$$\begin{matrix}& 2 & 5 & 4 & 1 & 0 & 0 & 0 \\ + &1 & 6 & 15 & 20 & 15 & 6 & 1 \\ \hline & 3 & 11 & 19 & 21 & 15 &6 & 1 \end{matrix}$$

The other two rows remain unchanged, save for the additional 0, so the next step would look like this:

$$ \begin{matrix} & + & - & + & - & + & - & +\\ A & 2 & 5 & 10 & 10 & 5 & 1 & 0 \\ B & 2 & 5 & \mathbf{6} & 4 & 1 & 0 & 0 \\ C & 3 & 11 & 19 & 21 & 15 &6 & 1 \end{matrix} \\ abccbac $$

and the next turn would go to b. This same basic idea can be applied to any number of players.

EDIT: I was externally asked to include some pseudo code. So there you go:

Definitions:

Let ${n\choose k} = \frac{n!}{k!\left(n-k\right)!}$ be the usual binomial coefficient.
Let ${\text{turn}_n}{\left(\tau\right)}$ be the $\tau^\text{th}$ turn in a game of $n$ players.
Let ${P^\tau}{\left(\epsilon\right)}$ be the polynomial $\left(1-\epsilon\right)^\tau$, associated with turn $\tau$.
Let $P_k^\tau$ be the $k^\text{th}$ coefficient of $P^\tau$: $\left(-1\right)^k {\tau \choose k}$.
Let $_iP^\tau$ be the polynomial of the $i^\text{th}$ player.
Let $_iP_k^\tau$ be the $k^\text{th}$ coefficient of $_iP^\tau$.

Initialize:

$_iP^0 = 0$

for each turn $\tau$, do:

find the player $i$ where the coefficient $_iP_0^\tau$ is minimal.
If multiple qualify, discard the disqualified ones, and check the next coefficient $_iP_1^\tau$ of the remaining players, and so on.
If a subset of players have the exact same associated polynomial $_iP^\tau$, arbitrarily pick the first one. (This will only happen initially and define the turn order.)
${\text{turn}_n}{\left(\tau\right)}=i$
$_iP^{\tau+1} = {_iP^\tau} + P^\tau$
$i$ here is only the minimal-coefficient player $i$ found before! Not all of them.

Next, here is a Python implementation (I'm sure there are plenty of ways to optimize this still, aside from just finding a proper recursion or substitution solution):

import functools
from itertools import count


@functools.lru_cache(maxsize=None)
def binomial_coeff(n, k):

    if n < 0:
        return 0
    if k > n // 2:
        return binomial_coeff(n, n - k)
    if k < 0:
        return 0
    if k == 0:
        return 1
    if k == 1:
        return n
    return binomial_coeff(n-1, k-1) + binomial_coeff(n-1, k)


def turns(player_count):
    # first n turns are always just the the players in standard order
    sequence = [turn for turn in range(player_count)]
    yield from sequence
    # setting up state to where it would be after first n turns plus some house keeping
    players = [[1, 0] for _ in range(player_count)]
    column_turn_number = [player_count, 1]
    column = 1
    sign = -1
    # once that's done, for every turn,
    for turn_number in count(player_count):
        # start with updating the current column to the most recent state
        for turn in range(column_turn_number[column], turn_number):
            players[sequence[turn]][column] += sign * binomial_coeff(turn, column)
            column_turn_number[column] += 1
        # then search for all occurrences of the minimum value in that column
        target_column = [player[column] for player in players]
        min_in_column = min(target_column)
        duplicates = [duplicate[0] for duplicate in
                      filter(lambda x: x[1] == min_in_column, enumerate(target_column))]
        # if there are more than one, then
        while len(duplicates) > 1:
            column += 1  # move to the next column and update it
            sign *= -1  # and update the sign accordingly
            try:
                for turn in range(column_turn_number[column], turn_number):
                    players[sequence[turn]][column] += sign * binomial_coeff(turn, column)
                    column_turn_number[column] += 1
            except IndexError:  # if it doesn't exist yet, just add a new column and try again
                for player in players:
                    player.append(0)
                    column_turn_number.append(column)
                for turn in range(column_turn_number[column], turn_number):
                    players[sequence[turn]][column] += sign * binomial_coeff(turn, column)
                    column_turn_number[column] += 1
            target_column = [players[index][column] for index in duplicates]
            min_in_column = min(target_column)
            duplicates = [duplicate[0] for duplicate in
                          filter(lambda x: x[1] == min_in_column, zip(duplicates, target_column))]
        turn = duplicates[0]  # once all duplicates are gone, the remaining value is your next turn
        yield turn  # return the turn,
        sequence.append(turn)  # store it for future reference, and
        column, sign = 0, 1  # reset the column and sign

Be careful: The way I implemented this, It's lazily generating more and more elements as I request them. If you try generating a list via list-comprehension it'll try generating the entire list for you which, it being infinitely long, will crash your computer.
Instead, use it like this:

turn = turns(3)  #  "3" for 3 players
print([next(turn) for _ in range(99)])  #  "99" for 99 turns

This will give you the first 99 turns for 3 players:

>>> [0, 1, 2, 2, 1, 0, 2, 1, 0, 0, 1, 2, 1, 2, 0, 0, 2, 1, 0, 2, 1, 1, 2, 0, 2, 1, 0, 0, 1, 2, 1, 0, 2, 2, 0, 1, 0, 2, 1, 1, 2, 0, 2, 1, 0, 0, 1, 2, 1, 0, 2, 2, 0, 1, 0, 2, 1, 1, 2, 0, 1, 2, 0, 0, 2, 1, 0, 2, 1, 1, 2, 0, 2, 1, 0, 0, 1, 2, 0, 1, 2, 2, 1, 0, 2, 1, 0, 0, 1, 2, 1, 0, 2, 2, 0, 1, 2, 0, 1]

Here are the first 100 turns for four players:

>>> [0, 1, 2, 3, 3, 2, 1, 0, 3, 2, 1, 0, 0, 1, 2, 3, 2, 1, 3, 0, 0, 3, 1, 2, 0, 3, 1, 2, 2, 1, 3, 0, 1, 3, 2, 0, 0, 2, 3, 1, 2, 0, 3, 1, 1, 3, 0, 2, 3, 1, 0, 2, 2, 0, 1, 3, 0, 1, 2, 3, 3, 2, 1, 0, 2, 1, 3, 0, 0, 3, 1, 2, 3, 0, 1, 2, 2, 1, 0, 3, 1, 2, 0, 3, 3, 0, 2, 1, 0, 2, 3, 1, 1, 3, 2, 0, 3, 2, 1, 0]

and, to show that it also generates Thue-Morse, here are the first 100 turns for two players:

>>> [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0]

As you can see, none of the various series in my question actually are the fairest possible turn order. None of them start $0, 1, 2, 2, 1, 0$.

Open subjects:

are there nice substitution or recursion rules to generate the n-player series in this sense?
are there other reasonable notions of "fair" turn order which result in different sequences?

EDIT: I tried plotting what happens for a large number of players $n$. Unfortunately I can't check with sufficient resolution but I conjecture that, as $n$ approaches $\infty$, each subset of $2n$ turns (excluding turns in previous subsets, so the set of turns $0\dots 2n-1$, $2n\dots 4n-1$, etc.) gives a (in the player limit) continuous boundary that ought to likely look fractal. (in the limit of turns $2n + i | i \in \left\{0\dots 2n-1 \right\} , n \to \infty$)

With the code as stated I fairly quickly run into memory problems, but here are the first few thousand turns that my computer could handle.

Note how each image is mirror symmetric. This is true for every $2n$ turns with $n$ players. To get much farther (more players, more turns) I need a more efficient approach.

$128$ players, moves $0 - 4607$, in chunks of $256 \ (= 2\times 128)$ moves each. Horizontal axis denotes turn, vertical the player ID (labelled from $0-127$).

(There is no text past these images.)