[Math] Does this sequence have any mathematical significance

sequences-and-series

Take the sequence 001 and repeatedly append its second half to itself, using the larger half if the length is odd. This gives you 00101 then 00101101 then 001011011101 then 001011011101011101 and so on. Counting the groups of adjacent ones gives 1 2 3 1 3 2 1 3 4 2 1 3 2 3 4.... You get similar results if you start off with other short sequences like 0010.

These sequences do not appear to repeat or follow an obvious pattern, yet they are generated from an extremely simple rule, similar to the Thue-Morse sequence or the look-and-say sequence. However, my sequence does not seem to be on OEIS.

I find it hard to believe that I'm the first person to think that appending half of a sequence to itself might be interesting. So my question is do these sequences already have a place in mathematics, however esoteric? If not, then why not? Am I wrong in thinking that this easily defined yet seemingly disorderly sequence is somewhat curious?

Related Questions:

Do runs of every length occur in this string?

Do runs of every length occur in this string? (At Math Overflow)

Where are the runs in this infinite string? (At Programming Puzzles & Code Golf)

Best Answer

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.

Related Solutions

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

Does the fraction of distinct substrings in prefixes of the Thue–Morse sequence of length $2^n$ tend to $73/96$

It should be easy to derive the conjecture from the results of [1]. In particular, Brlek gives in Proposition 4.2 the precise value of the number $P(n,m)$ of factors of length $m$ of $p_n$ (up to the empty word, which is not included). But more interestingly, he gives a table of the small values of $P_n(m)$. Here is this table (I added the empty word in the first column): \begin{array}{c|cc} n \backslash m & 0& 1 & 2 & 3 & 4 & 5 &6 & 7 & 8 & 9 & 10 & 11 & 12 &13 &14 &15 &16 &17 &18 &19 &20 &21 \\ \hline 1&1&2&1\\ 2&1&2&\mathbf{3}&2&1\\ 3&1&2&4&\mathbf{6}&5&4&3&2&1\\ 4&1&2&4&6&10&\mathbf{12}&11&10&9&8&7&6&5&4&3&2&1\\ 5&1&2&4&6&10&12&16&20&22&\mathbf{24}&23&22&21&20&19&18&17&16&15&14&13&12& \dotsm\\ 6&1&2&4&6&10&12&16&20&22&24&28&32&36&40&42&44&46&\mathbf{48}&47&46&45&44& \dotsm \end{array}

As you can see, there are two types of coefficients in this table. Starting from the coefficients in bold, in position $(k, 2^{k-2} + 1)$ for $k > 0$ (that is $\mathbf{6}$, $\mathbf{12}$, $\mathbf{24}$, $\mathbf{48}$, etc.) the coefficients decrease by $1$ in each line. Thus it is easy to take the sum of these coefficients.

The other coefficients, apart from the first values of $m$, also follow a regular pattern. One has $P(n,m) = P(n-1,m)$ for $m \leqslant 2^{n-3}$. Then the coefficients between $P(n, 2^{n-3} + 1)$ and $P(n, 2^{n-3} + 2^{n-4} + 1)$ form an arithmetic progression of reason $4$ (see $24, 28, 32, 36, 40$ in line 6) and then the coefficients between $P(n, 2^{n-3} + 2^{n-4} + 1)$ and $P(n, 2^{n-2} + 1)$ form an arithmetic progression of reason $2$ (see $40,42,44,46,48$ in line 6).

I am a bit lazy to make the complete computation but, with these observations in hand, it should not be too difficult to sum up the coefficients in each line to get the value of ${\cal D}_n$.

[1] S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Applied Math. 24 (1989), 83-96.