Is This An Efficient Way To Generate The Thue-morse Sequence In Python?

Is using a generator as in the code below, an efficient way to generate the Thue-Morse sequence in Python? # generate the Thue-Morse sequence def genThueMorse(): # initialize

Solution 1:

This is concise, is it "efficient"?

import itertools

defgenThueMorse():
    for n in itertools.count():
        yield (1ifbin(n).count('1')%2else0)

Solution 2:

I think a generator will be fairly efficient. I would go for something like this:

from itertools import count, izip

defgenThueMorse():
    tms = [0]
    invert = [1, 0]
    for tm, curr in izip(tms, count()):
        yieldstr(tm)
        if curr == len(tms) - 1:
            tms += [invert[c] for c in tms]

Solution 3:

Helping to complement the other answers: If you only want to calculate the nth digit in the sequence use:

lambda n: bin(n).count("1") % 2

or if prefer a function:

defcalculate_nth(n):
  returnbin(n).count("1") % 2

Example:

f = lambda n:  bin(n).count("1") % 2
f(0) # This will return 0
f(1) # This will return 1
f(2) # This will return 1
...
f(10) # This will return 0

This can be verified with the sequence: 011 0 1 0 0 1 1 0 0 1 0 1 1 0