In mathematics, the ThueâÂÂMorse or ProuhetâÂÂThueâÂÂMorse sequence is the binary sequence (an infinite sequence of s and s) that can be obtained by starting with and successively appending the Boolean complement of the sequence obtained thus far. It is sometimes called the fair share sequence because of its applications to fair division or parity sequence. The first few steps of this procedure yield the strings , , , , , and so on, which are the prefixes of the ThueâÂÂMorse sequence. The full sequence begins:
The sequence is named after Axel Thue, Marston Morse and (in its extended form) .
There are several equivalent ways of defining the ThueâÂÂMorse sequence.
To compute the th element , write the number in binary. If the number of ones in this binary expansion is odd then , if even then . That is, is the even parity bit for . John Conway et al. deemed numbers satisfying to be odious (intended to be similar to odd) numbers, and numbers for which to be evil (similar to even) numbers.
This method leads to a fast method for computing the ThueâÂÂMorse sequence: start with , and then, for each , find the highest-order bit in the binary representation of that is different from the same bit in the representation of . If this bit is at an even index, differs from , and otherwise it is the same as .
In Python:
The resulting algorithm takes constant time to generate each sequence element, using only a logarithmic number of bits (constant number of words) of memory.
The ThueâÂÂMorse sequence is the sequence satisfying the recurrence relation
for all non-negative integers .
The ThueâÂÂMorse sequence is a morphic word: 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. The first element is . Once the first elements have been specified, forming a string , then the next elements must form the bitwise negation of . Now we have defined the first elements, and we recurse.
Spelling out the first few steps in detail:
So
In Python:
Which can then be converted to a (reversed) string as follows:
A generating function for the sequence can be defined by:
where is the th element if we start at .
The ThueâÂÂMorse sequence contains many squares: instances of the string , where denotes the string , , , or , where for some and is the bitwise negation of . For instance, if , then . The square appears in starting at the 16th bit. Since all squares in are obtained by repeating one of these 4 strings, they all have length or for some . contains no cubes: instances of for any . There are also no overlapping squares: instances of or . The critical exponent of is .
The ThueâÂÂMorse sequence is a uniformly recurrent word: given any finite string in the sequence, there is some length (often much longer than the length of ) such that appears in every block of length . Notably, the ThueâÂÂMorse sequence is uniformly recurrent without being either periodic or eventually periodic (i.e., periodic after some initial nonperiodic segment).
The sequence is a palindrome for any . Furthermore, let be a word obtained by counting the ones between consecutive zeros in . For instance, and . Since does not contain overlapping squares, the words are palindromic squarefree words.
The ThueâÂÂMorse morphism is defined on alphabet by the substitution map , : every in a sequence is replaced with and every with . If is the ThueâÂÂMorse sequence, then is also . Thus, is a fixed point of . The morphism is a prolongable morphism on the free monoid with as fixed point: is essentially the only fixed point of ; the only other fixed point is the bitwise negation of , which is simply the ThueâÂÂMorse sequence on instead of on . This property may be generalized to the concept of an automatic sequence.
In the ThueâÂÂMorse sequence, the symbols and can be replaced with the variables and to obtain a generalized ThueâÂÂMorse sequence. If and are distinct positive integers, then the resulting sequence can be taken to be the terms of a simple continued fraction. The resulting ThueâÂÂMorse continued fraction,
is transcendental.
The set of evil numbers (numbers with ) 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 and a non-negative integer , partition the set into two disjoint subsets and that have equal sums of powers up to , that is:
This has a solution if is a multiple of , given by:
For example, for and ,
The condition requiring that be a multiple of 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 th powers of any set of 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 th 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".
Using turtle graphics, a curve can be generated if an automaton is programmed with a sequence. Using the ThueâÂÂMorse sequence, the rules
generate a curve that 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.
It is also possible to draw the curve precisely using the following instructions:
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.
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".
Robert Richman addressed this problem, but he too did not identify the ThueâÂÂMorse sequence as such at the time of publication. He presented the sequences as step functions on the interval and described their relationship to the Walsh and Rademacher functions. He showed that the th derivative can be expressed in terms of . As a consequence, the step function arising from is orthogonal to polynomials of order . 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.
Joshua Cooper and Aaron Dutle showed why the ThueâÂÂMorse order provides a fair outcome for discrete events. 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 of length , 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 or discretely.
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. He did a set of field experiments with pro players and found that the team kicking first won 60% of games using ABAB (or ), 54% using ABBA (or ), and 51% using full ThueâÂÂMorse (or ).àAs a result, ABBAàis undergoing extensive trials in FIFA (European and World Championships) and English Federation professional soccer (EFL Cup). An ABBA serving pattern has also been found to improve the fairness of tennis tie-breaks. In competitive rowing, 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 is one of only four rigs to avoid wiggle on an eight-membered boat.
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 ). Ian Allan argued that a "third-round reversal" (forward, backward, backward, forward, etc.; or ) would be even more fair. Richman suggested that the fairest way for "captain A" and "captain B" to choose sides for a pick-up game of basketball mirrors : captain A has the first, fourth, sixth, and seventh choices, while captain B has the second, third, fifth, and eighth choices.
The initial bits of the ThueâÂÂMorse sequence are mapped to by a wide class of polynomial hash functions modulo a power of two, which can lead to hash collisions.
Certain linear combinations of Dirichlet series whose coefficients are terms of the ThueâÂÂMorse sequence give rise to identities involving the Riemann Zeta function (Tóth, 2022). For instance:
where is the th term of the ThueâÂÂMorse sequence. In fact, for all with real part greater than , we have
The ThueâÂÂMorse sequence was first studied by in 1851, who applied it to number theory. However, Prouhet did not mention the sequence explicitly; this was left to Axel Thue in 1906, who used it to found the study of combinatorics on words. The sequence was only brought to worldwide attention with the work of Marston Morse in 1921, when he applied it to differential geometry. The sequence has been discovered independently many times, not always by professional research mathematicians; for example, Max Euwe, a chess grandmaster and mathematics teacher, discovered it in 1929 in an application to chess: by using its cube-free property (see above), he showed how to circumvent the threefold repetition rule aimed at preventing infinitely protracted games by declaring repetition of moves a draw. At the time, consecutive identical board states were required to trigger the rule; the rule was later amended to the same board position reoccurring three times at any point, as the sequence shows that the consecutive criterion can be evaded forever.