The [[Prouhet-Thue-Morse sequence]] (a.k.a. [[Thue-Morse sequence]]) is a fascinating and simple mathematical sequence that exhibits a complex and **non-repetitive structure**, despite being generated by a straightforward rule. This sequence is of great interest in various fields of mathematics, computer science, and theoretical computer science due to its unique properties and applications. It is named after the Norwegian mathematician [[Axel Thue]], who studied the sequence in the early 20th century, and [[Marston Morse]], who also explored its properties. According to [[Veikko Keränen]]: > Not many people mention [[Eugène Prouhet]] or even know about him. However, he was undoubtedly (as far as we know) the first to use the sequence in 1851. He did not study repetitions, though. ### Generation The Thue-Morse sequence is generated by starting with 0 and iteratively appending the binary complement of the sequence obtained so far. The binary complement of a sequence is obtained by swapping all 0s for 1s and all 1s for 0s. 1. Start with 0. 2. The complement of 0 is 1, so append it: the sequence becomes 01. 3. The complement of 01 is 10, so append it: the sequence becomes 0110. 4. The complement of 0110 is 1001, so append it: the sequence becomes 01101001. 5. This process is repeated indefinitely. This iterative process results in the infinite sequence: 0110100110010110... ### Properties - **Non-repetitive**: The Thue-Morse sequence is remarkable for its avoidance of cubes, which are three consecutive repetitions of a substring, making it "**cube-free**." It also avoids overlapping squares, a property that made it a subject of extensive study in combinatorics on words. - **Self-similarity**: The sequence is fractal-like, meaning it contains copies of itself at various scales. - **Balanced**: In any finite prefix of the Thue-Morse sequence, the number of 0s and 1s differ by at most one. This property is known as being "balanced." - **Fair sharing sequence**: If two people were to take turns in a binary sequence to ensure fairness, the Thue-Morse sequence would be an optimal strategy, as it minimizes the discrepancies in the distribution of 0s and 1s over any part of the sequence. ### Applications The Thue-Morse sequence has found applications in a variety of domains: - **Mathematics**: It serves as a counterexample in several mathematical problems and has been used to study the structure of certain algebraic objects. - **Computer Science**: Its properties of **non-repetition** have implications for algorithms and data structures, especially those involving pattern matching and avoidance. - **Music and Art**: The sequence's structure has inspired compositions and artworks that explore patterns and [[Repetition]]. The Thue-Morse sequence's simplicity in generation contrasts with the deep and wide-ranging implications of its properties, making it a subject of ongoing interest and study in theoretical and applied disciplines. # References ```dataview Table title as Title, authors as Authors where contains(subject, "Thue-Morse sequence" ) or contains(subject, "square-free" ) or contains(subject, "overlap-free" ) or contains(subject, "cube-free" ) sort modified desc, subject, title ```