Thue–Morse sequence
In
- 01101001100101101001011001101001.... [1]
The sequence is named after Axel Thue and Marston Morse.
Definition
There are several equivalent ways of defining the Thue–Morse sequence.
Direct definition
To compute the nth element tn, write the number n in
Fast sequence generation
This method leads to a fast method for computing the Thue–Morse sequence: start with t0 = 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, tn differs from tn − 1, and otherwise it is the same as tn − 1.
In Python:
def generate_sequence(seq_length: int):
"""Thue–Morse sequence."""
value = 1
for n in range(seq_length):
# Note: assumes that (-1).bit_length() gives 1
x = (n ^ (n - 1)).bit_length() + 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]
Recurrence relation
The Thue–Morse sequence is the sequence tn satisfying the recurrence relation
for all non-negative integers n.[2]
L-system
The Thue–Morse sequence is a morphic word:[4] it is the output of the following Lindenmayer system:
Variables | 0, 1 |
---|---|
Constants | None |
Start | 0 |
Rules | (0 → 01), (1 → 10) |
Characterization using bitwise negation
The Thue–Morse sequence in the form given above, as a sequence of
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
- T0 = 0.
- T1 = 01.
- T2 = 0110.
- T3 = 01101001.
- T4 = 0110100110010110.
- T5 = 01101001100101101001011001101001.
- T6 = 0110100110010110100101100110100110010110011010010110100110010110.
- And so on.
Infinite product
The sequence can also be defined by:
where tj is the jth element if we start at j = 0.
Properties
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 .[5] 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 . There are also no overlapping squares: instances of or .[6][7] The critical exponent of is 2.[8]
The Thue–Morse sequence is a
The sequence T2n is a
The Thue–Morse
The generating series of T over the
This power series is algebraic over the field of rational functions, satisfying the equation[13]
In combinatorial game theory
The set of evil numbers (numbers with ) forms a subspace of the nonnegative integers under
The Prouhet–Tarry–Escott problem
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 S0 and S1 that have equal sums of powers up to k, that is:
- for all integers i from 1 to k.
This has a solution if N is a multiple of 2k+1, given by:
- S0 consists of the integers n in S for which tn = 0,
- S1 consists of the integers n in S for which tn = 1.
For example, for N = 8 and k = 2,
- 0 + 3 + 5 + 6 = 1 + 2 + 4 + 7,
- 02 + 32 + 52 + 62 = 12 + 22 + 42 + 72.
The condition requiring that N be a multiple of 2k+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]
Fractals and turtle graphics
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.
Equitable sequencing
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.
Joshua Cooper and Aaron Dutle showed why the Thue–Morse order provides a fair outcome for discrete events.
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.
Fairness is especially important in
Hash collisions
The initial 2k 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]
Riemann zeta function
Certain linear combinations of Dirichlet series whose coefficients are terms of the
where is the term of the Thue-Morse sequence. In fact, for all with real part greater than , we have
History
The Thue–Morse sequence was first studied by Eugène Prouhet in 1851,[30] 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.
See also
- Dejean's theorem
- Fabius function
- First difference of the Thue–Morse sequence
- Gray code[31][32]
- Komornik–Loreti constant
- Prouhet–Thue–Morse constant
Notes
- ^ a b Sloane, N. J. A. (ed.). "Sequence A010060 (Thue-Morse sequence)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
- ^ a b Allouche & Shallit (2003, p. 15)
- ^ Arndt (2011).
- ^ Lothaire (2011, p. 11)
- ^ Brlek (1989).
- ^ Lothaire (2011, p. 113)
- ^ Pytheas Fogg (2002, p. 103)
- ^ Krieger (2006).
- ^ Lothaire (2011, p. 30)
- ^ Berthé & Rigo (2010).
- ^ Lothaire (2011, p. 31)
- ^ Berstel et al. (2009, p. 70)
- ^ Berstel et al. (2009, p. 80)
- ^ Bolker et al. (2016).
- ^ Ma & Holdener (2005).
- ^ Abel, Zachary (January 23, 2012). "Thue-Morse Navigating Turtles". Three-Cornered Things.
- ^ Brams & Taylor (1999).
- ^ Levine & Stange (2012).
- ^ a b c Richman (2001)
- ^ Abrahams (2010).
- ^ a b Cooper & Dutle (2013)
- ^ Palacios-Huerta (2012).
- ^ Palacios-Huerta (2014).
- ^ Cohen-Zada, Krumer & Shapir (2018).
- ^ Barrow (2010).
- ^ "Fantasy Draft Types". NFL.com. Archived from the original on October 12, 2018.
- ^ Allan, Ian (July 16, 2014). "Third-Round Reversal Drafts". Fantasy Index. Retrieved September 1, 2020.
- ^ Pachocki, Jakub; Radoszewski, Jakub (2013). "Where to Use and How not to Use Polynomial String Hashing" (PDF). Olympiads in Informatics. 7: 90–100.
- ^
arXiv:2211.13570.
- ^ The ubiquitous Prouhet-Thue-Morse sequence by Jean-Paul Allouche and Jeffrey Shallit
- ^ Fredricksen, Harold (1992). "Gray codes and the Thue-Morse-Hedlund sequence". Journal of Combinatorial Mathematics and Combinatorial Computing (JCMCC). 11. Naval Postgraduate School, Department of Mathematics, Monterey, California, USA: 3–11.
- ^ Erickson, John (2018-10-30). "On the Asymptotic Relative Change for Sequences of Permutations". Retrieved 2021-01-31. [1]
References
- Abrahams, Marc (12 July 2010). "How to pour the perfect cup of coffee". The Guardian.
- Arndt, Jörg (2011). "1.16.4 The Thue–Morse sequence" (PDF). Matters Computational: Ideas, Algorithms, Source Code. Springer. p. 44.
- Allouche, Jean-Paul; Zbl 1086.11015.
- Barrow, John D. (2010). "Rowing and the Same-Sum Problem Have Their Moments". S2CID 119207447.
- Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. Vol. 27. Providence, RI, USA: Zbl 1161.68043.
- Zbl 1197.68006.
- Bolker, Ethan; Offner, Carl; Richman, Robert; Zara, Catalin (2016). "The Prouhet–Tarry–Escott problem and generalized Thue–Morse sequences". Journal of Combinatorics. 7 (1): 117–133. S2CID 118040795.}
- Brams, Steven J.; Taylor, Alan D. (1999). The Win-Win Solution: Guaranteeing Fair Shares to Everybody. W. W. Norton & Co., Inc. pp. 36–44. ISBN 978-0-393-04729-5.
- Brlek, Srećko (1989). "Enumeration of Factors in the Thue-Morse Word". .
- Cohen-Zada, Danny; Krumer, Alex; Shapir, Offer Moshe (2018). "Testing the effect of serve order in tennis tiebreak". S2CID 89610106.
- Cooper, Joshua; Dutle, Aaron (2013). "Greedy Galois Games" (PDF). S2CID 1291901.
- Krieger, Dalia (2006). "On critical exponents in fixed points of non-erasing morphisms". In Ibarra, Oscar H.; Dang, Zhe (eds.). Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, California, USA, June 26-29, 2006. Lecture Notes in Computer Science. Vol. 4036. Zbl 1227.68074.
- Levine, Lionel; Stange, Katherine E. (2012). "How to Make the Most of a Shared Meal: Plan the Last Bite First" (PDF). S2CID 14537479.
- Zbl 1221.68183.
- Ma, Jun; MR 2166279.
- Palacios-Huerta, Ignacio (2012). "Tournaments, fairness and the Prouhet–Thue–Morse sequence" (PDF). Economic Inquiry. 50 (3): 848–849. S2CID 54036493.
- Palacios-Huerta, Ignacio (2014). Beautiful Game Theory. Princeton University Press. ISBN 978-0691144023.
- Pytheas Fogg, N. (2002). Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Berlin, Germany: Zbl 1014.11015.
- Richman, Robert (2001). "Recursive Binary Sequences of Differences" (PDF). Complex Systems. 13 (4): 381–392.
Further reading
- Bugeaud, Yann (2012). Distribution modulo one and Diophantine approximation. Cambridge Tracts in Mathematics. Vol. 193. Cambridge: Zbl 1260.11001.
- Zbl 1133.68067.
External links
- "Thue-Morse sequence", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
- Weisstein, Eric W. "Thue-Morse Sequence". MathWorld.
- Allouche, J.-P.; Shallit, J. O. The Ubiquitous Prouhet-Thue-Morse Sequence. (contains many applications and some history)
- Thue–Morse Sequence over (1,2) (sequence A001285 in the OEIS)
- OEIS sequence A000069 (Odious numbers: numbers with an odd number of 1's in their binary expansion)
- OEIS sequence A001969 (Evil numbers: numbers with an even number of 1's in their binary expansion)
- Reducing the influence of DC offset drift in analog IPs using the Thue-Morse Sequence. A technical application of the Thue–Morse Sequence
- MusiNum - The Music in the Numbers. Freeware to generate self-similar music based on the Thue–Morse Sequence and related number sequences.
- Parker, Matt. "The Fairest Sharing Sequence Ever" (video). standupmaths. Retrieved 20 January 2016.