ThueMorsesekvensen

ThueMorsesekvensen, also known as the Thue-Morse sequence, is an infinite binary sequence of 0s and 1s. It is named after Axel Thue and Marston Morse. The sequence is constructed iteratively. It begins with 0. The next step is to append the bitwise complement of the current sequence. So, starting with 0, the sequence becomes 01. Appending the complement of 01 (which is 10) gives 0110. Appending the complement of 0110 (which is 1001) results in 01101001. This process is repeated indefinitely. The nth term of the sequence is 0 if the sum of the binary digits of n is even, and 1 if the sum of the binary digits of n is odd.

The Thue-Morse sequence has many interesting mathematical properties. It is known for being cube-free, meaning it does not contain any substring of the form xxx for any non-empty string x. For example, it does not contain 000 or 111. It is also known for its low complexity. The number of distinct blocks of length n in the Thue-Morse sequence grows linearly with n. The sequence also exhibits a form of self-similarity. It can be generated by a system of recurrence relations. The Thue-Morse sequence has applications in various fields, including combinatorics on words, theoretical computer science, and fractal geometry.

---