Thue-Morse Sequence generator¶

Try me¶

Problem definition¶

The Thue Morse Sequence is a binary sequence that is generated by negating (binary complement) the bits in the sequence so far, and appending the resulting bits to the sequence, starting with 0. That is, the sequence is built iteratively like this: 0, 01, 0110, 01101001, … Notice that the new bits added in every sequence step are the binary complement of the sequence. You can find more information about the Thue-Morese Sequence here. Can you create a Thue-More sequence generator in Python?

Solution¶

Our strategy is based on calculating the binary complement of a number:

[3]:

n = int(input("Please enter a number: "))
thue_morse = [0]

for i in range(1, n):
    next_sequence = []
    for x in thue_morse:
        next_sequence.append(1-x)
    thue_morse.extend(next_sequence)
print(thue_morse)

Ok, so there we have basic solution, but can we get the same result using bit-wise operations? Let’s try it, but only if you have some brain cells left to spare:

[4]:

n_steps = int(input("Specify the number of steps: "))
thue_morse = [0]
for i in range(1, n):
    thue_morse.extend([1-x for x in thue_morse])

print(thue_morse)

In this solution, we use list comprehension (check the second tutorial on iterables). Finally, we join the list to the original list using and append it to the sequence (check the string section of the tutorials on strings).

Analysis questions¶

Initialization: How is the Thue-Morse sequence initialized in the code? What’s the significance of starting with this value? What happens if you change the initial value?
Iteration: Describe the steps the code takes to build the Thue-Morse sequence iteratively.
Bitwise Binary Complement: What does the line next_sequence.append(1-x) achieve? Can you modify the code to use bitwise negation instead of arithmetic negation?
Flow of Control: If n is set to 3, how many iterations does the for loop run? And what is the output? How does the length of the thue_morse list change with each iteration?
Efficiency: Discuss the time complexity of this code. If n is increased by 1, how does the length of the resulting Thue-Morse sequence change?
Applications: The Thue-Morse sequence is known for its lack of runs (long sequences of alternative numbers). Can you think of any applications where this property might be useful?