Thue-Morse Sequence

Problem

Return the first n characters of the Thue-Morse sequence, which starts with 0 and repeatedly appends the bitwise complement of everything produced so far.

The sequence begins 0, 1, 1, 0, 1, 0, 0, 1. Return the empty string for n <= 0.

Hint

Each doubling step maps every 0 to 1 and every 1 to 0.

Test cases

case 1

in: [0]

expected: ""

case 2

in: [1]

expected: "0"

case 3

in: [4]

expected: "0110"

case 4

in: [8]

expected: "01101001"

case 5

in: [16]

expected: "0110100110010110"

Starter codePython

def thue_morse(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor