Thue–Morse sequence

When counting in binary, the digit sum modulo 2 is the Thue–Morse sequence

To compute the nth element t_n, write the number n in binary. If the number of ones in this binary expansion is odd then t_n = 1, if even then t_n = 0.[2] That is, t_n is the even parity bit for n. John H. Conway et al. called numbers n satisfying t_n = 1 odious (for odd) numbers and numbers for which t_n = 0 evil (for even) numbers. In other words, t_n = 0 if n is an evil number and t_n = 1 if n is an odious number.

This method leads to a fast method for computing the Thue–Morse sequence: start with t₀ = 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, t_n differs from t_n − 1, and otherwise it is the same as t_n − 1.

In pseudo-code form:

def generate_sequence(seq_length: int):
    """Thue–Morse sequence."""
    value = 0
    for n = 0 to seq_length-1 by 1:
        # Note: assumes an even number of bits in the word size, and two's complement arithmetic so that when n == 0, x is odd (e.g. 31 or 63)
        x = index_of_highest_one_bit(n ^ (n - 1))                        
        if ((x & 1) == 0):
            # bit index is even, so toggle value
            value = 1 - value
        yield value

The resulting algorithm takes constant time to generate each sequence element, using only a logarithmic number of bits (constant number of words) of memory.[3]

The Thue–Morse sequence is the sequence t_n satisfying the recurrence relation

${\displaystyle {\begin{aligned}t_{0}&=0,\\t_{2n}&=t_{n},\\t_{2n+1}&=1-t_{n},\end{aligned}}}$

for all non-negative integers n.[2]

Thue–Morse sequence generated by an L-System

The Thue–Morse sequence is a morphic word:[4] it is the output of the following Lindenmayer system:

The Thue–Morse sequence in the form given above, as a sequence of bits, can be defined recursively using the operation of bitwise negation. So, the first element is 0. Then once the first 2ⁿ elements have been specified, forming a string s, then the next 2ⁿ elements must form the bitwise negation of s. Now we have defined the first 2ⁿ⁺¹ elements, and we recurse.

Spelling out the first few steps in detail:

• We start with 0.
• The bitwise negation of 0 is 1.
• Combining these, the first 2 elements are 01.
• The bitwise negation of 01 is 10.
• Combining these, the first 4 elements are 0110.
• The bitwise negation of 0110 is 1001.
• Combining these, the first 8 elements are 01101001.
• And so on.

So

• T₀ = 0.
• T₁ = 01.
• T₂ = 0110.
• T₃ = 01101001.
• T₄ = 0110100110010110.
• T₅ = 01101001100101101001011001101001.
• T₆ = 0110100110010110100101100110100110010110011010010110100110010110.
• And so on.

The sequence can also be defined by:

${\displaystyle \prod _{i=0}^{\infty }\left(1-x^{2^{i}}\right)=\sum _{j=0}^{\infty }(-1)^{t_{j}}x^{j},}$

where t_j is the jth element if we start at j = 0.

The set of evil numbers (numbers ${\displaystyle n}$ with ${\displaystyle t_{n}=0}$) forms a subspace of the nonnegative integers under nim-addition (bitwise exclusive or). For the game of Kayles, evil nim-values occur for few (finitely many) positions in the game, with all remaining positions having odious nim-values.

The Prouhet–Tarry–Escott problem can be defined as: given a positive integer N and a non-negative integer k, partition the set S = { 0, 1, ..., N-1 } into two disjoint subsets S₀ and S₁ that have equal sums of powers up to k, that is:

${\displaystyle \sum _{x\in S_{0}}x^{i}=\sum _{x\in S_{1}}x^{i}}$ for all integers i from 1 to k.

This has a solution if N is a multiple of 2^k+1, given by:

• S₀ consists of the integers n in S for which t_n = 0,
• S₁ consists of the integers n in S for which t_n = 1.

For example, for N = 8 and k = 2,

0 + 3 + 5 + 6 = 1 + 2 + 4 + 7,

0² + 3² + 5² + 6² = 1² + 2² + 4² + 7².

The condition requiring that N be a multiple of 2^k+1 is not strictly necessary: there are some further cases for which a solution exists. However, it guarantees a stronger property: if the condition is satisfied, then the set of kth powers of any set of N numbers in arithmetic progression can be partitioned into two sets with equal sums. This follows directly from the expansion given by the binomial theorem applied to the binomial representing the nth element of an arithmetic progression.

For generalizations of the Thue–Morse sequence and the Prouhet–Tarry–Escott problem to partitions into more than two parts, see Bolker, Offner, Richman and Zara, "The Prouhet–Tarry–Escott problem and generalized Thue–Morse sequences".[14]

Using turtle graphics, a curve can be generated if an automaton is programmed with a sequence. When Thue–Morse sequence members are used in order to select program states:

• If t(n) = 0, move ahead by one unit,
• If t(n) = 1, rotate by an angle of π/3 radians (60°)

The resulting curve converges to the Koch curve, a fractal curve of infinite length containing a finite area. This illustrates the fractal nature of the Thue–Morse Sequence.[15]

It is also possible to draw the curve precisely using the following instructions:[16]

• If t(n) = 0, rotate by an angle of π radians (180°),
• If t(n) = 1, move ahead by one unit, then rotate by an angle of π/3 radians.

In their book on the problem of fair division, Steven Brams and Alan Taylor invoked the Thue–Morse sequence but did not identify it as such. When allocating a contested pile of items between two parties who agree on the items' relative values, Brams and Taylor suggested a method they called balanced alternation, or taking turns taking turns taking turns . . . , as a way to circumvent the favoritism inherent when one party chooses before the other. An example showed how a divorcing couple might reach a fair settlement in the distribution of jointly-owned items. The parties would take turns to be the first chooser at different points in the selection process: Ann chooses one item, then Ben does, then Ben chooses one item, then Ann does.[17]

Lionel Levine and Katherine E. Stange, in their discussion of how to fairly apportion a shared meal such as an Ethiopian dinner, proposed the Thue–Morse sequence as a way to reduce the advantage of moving first. They suggested that “it would be interesting to quantify the intuition that the Thue–Morse order tends to produce a fair outcome.”[18]

Robert Richman addressed this problem, but he too did not identify the Thue–Morse sequence as such at the time of publication.[19] He presented the sequences T_n as step functions on the interval [0,1] and described their relationship to the Walsh and Rademacher functions. He showed that the nth derivative can be expressed in terms of T_n. As a consequence, the step function arising from T_n is orthogonal to polynomials of order n − 1. A consequence of this result is that a resource whose value is expressed as a monotonically decreasing continuous function is most fairly allocated using a sequence that converges to Thue–Morse as the function becomes flatter. An example showed how to pour cups of coffee of equal strength from a carafe with a nonlinear concentration gradient, prompting a whimsical article in the popular press.[20]

Joshua Cooper and Aaron Dutle showed why the Thue–Morse order provides a fair outcome for discrete events.[21] They considered the fairest way to stage a Galois duel, in which each of the shooters has equally poor shooting skills. Cooper and Dutle postulated that each dueler would demand a chance to fire as soon as the other's a priori probability of winning exceeded their own. They proved that, as the duelers’ hitting probability approaches zero, the firing sequence converges to the Thue–Morse sequence. In so doing, they demonstrated that the Thue–Morse order produces a fair outcome not only for sequences T_n of length 2ⁿ, but for sequences of any length.

Thus the mathematics supports using the Thue–Morse sequence instead of alternating turns when the goal is fairness but earlier turns differ monotonically from later turns in some meaningful quality, whether that quality varies continuously[19] or discretely.[21]

Sports competitions form an important class of equitable sequencing problems, because strict alternation often gives an unfair advantage to one team. Ignacio Palacios-Huerta proposed changing the sequential order to Thue–Morse to improve the ex post fairness of various tournament competitions, such as the kicking sequence of a penalty shoot-out in soccer.[22] He did a set of field experiments with pro players and found that the team kicking first won 60% of games using ABAB (or T₁), 54% using ABBA (or T₂), and 51% using full Thue–Morse (or T_n).  As a result, ABBA is undergoing extensive trials in FIFA (European and World Championships) and English Federation professional soccer (EFL Cup).[23] An ABBA serving pattern has also been found to improve the fairness of tennis tie-breaks.[24] In competitive rowing, T₂ is the only arrangement of port- and starboard-rowing crew members that eliminates transverse forces (and hence sideways wiggle) on a four-membered coxless racing boat, while T₃ is one of only four rigs to avoid wiggle on an eight-membered boat.[25]

Fairness is especially important in player drafts. Many professional sports leagues attempt to achieve competitive parity by giving earlier selections in each round to weaker teams. By contrast, fantasy football leagues have no pre-existing imbalance to correct, so they often use a “snake” draft (forward, backward, etc.; or T₁).[26] Ian Allan argued that a “third-round reversal” (forward, backward, backward, forward, etc.; or T₂) would be even more fair.[27] Richman suggested that the fairest way for “captain A” and “captain B” to choose sides for a pick-up game of basketball mirrors T₃: captain A has the first, fourth, sixth, and seventh choices, while captain B has the second, third, fifth, and eighth choices.[19]

The initial 2^k bits of the Thue–Morse sequence are mapped to 0 by a wide class of polynomial hash functions modulo a power of two, which can lead to hash collisions.[28]