Problem 5- thuemorse.py: Thue-Morse sequence [25 points] A sequence with many interesting peoperties is the Thue-Morse sequence . which is defined as follows: . The level-0 sequence so is simply 0. . The level-1) sequence consists of the level- sequence st, with it's bitwise negation S. i.e., A perfect square is an integer which can be written as the square of another integer. For example, the first five perfect squares are 1,4, 9 6, and 25 (since each is equal to 1,22,34and5respectively. You could also breax within a for loop, but a while loop is a more natural way to express that logic. Eg.see httpsi//es.uwaterloo.ca/-shallit/Talks/green3.pd for a presentation on these, and more. 'https: //en. wikipedia.org/wiki/Thue E2#80893Morse.-sequence 33:136:388- Spring 2018 Homework 2 Due date: 11/2 Given a binary string s, it's bitwise negation 3 is simply the string of the same length that we obtain by flipping every 0 to 1 and every 1 to 0. For example, if s101011 then 010100. Working out the definition of the Thue-Morse sequence, the first few of it's levels are: O. so = 0. 1. The negation of O is 1, so if we concatenate them together we get s101 2. The negation of 01 S, s 10 3. The negation of mathtt010s is 1001 , so if we concatenate them together we get s? 0110. so if we concatenate them together we get s3- 01101001. 4. The negation of 01101001 S3 S 10010110 , so if we concatenate them together we get s4 = 0110100110010110. 5. Write a program that takes a non-negative integer argument which is the level Morse sequence st and prints the coeresponding Thue- Hint: You could write a loop to manipulate a 0-1 string and produce it's bitwise negation. However, you can write a simpler program if you observe that + can also be expressed in terms of s and st using a simple concatenation (rather than in terms of s-1 using a non-trivial bitwise negation). Figuring out that relationship obviates the need to implement bitwise negation. Instead, your loop can progressively constructs both sl andconcurrently? In other words, you will need to update two variables, "in lockstep", one holding sg and another holding S Practice goal: This problem is related to the construction of the "subdivisions of a (binary) ruler", in that the next level is defined in terms of the previous level Further practice with running different accumulations "in lockstep" within the same loop