#!/usr/bin/env sage -python
#
# Computes the Thue-Morse sequence, constant, polynomial,
# and word over the {0,1} alphabet.
#
# The Thue-Morse sequence t_n is defined as
# t_0 = 0, t_1 = 1, t_{2n} = t_n, t_{2n+1} = 1-t_n for n >= 0.
#
# Stephen Forrest, http://wandership.ca/

import sys
from sage.all import * 

def ilog(x, base=math.e):
    i = 0
    if x < 1 and base < 1:
        raise ValueError, "logarithm cannot compute"
    while x < 1:
        i -= 1
        x *= base
    while x >= base:
        i += 1
        x /= base
    return i

# Compute the Thue-Morse sequence
def ThueMorse_Compute(n):
    TM = [0,1]
    def minus1(x): return(1-x)
    for i in range(1,ilog(n-1,2)+1):
        TM.extend( map( minus1, TM ) )
    return TM

def tm_poly(x,n):
    TM = ThueMorse_Compute(n)
    p = 0
    for i in range(0,n):
        p += TM[i]*x**i
    return p

# Return the Thue-Morse polynomial (over the integers)
def ThueMorse_Polynomial(n):
    R = PolynomialRing(ZZ,'x')
    return tm_poly(R.gen(),n)

# Return the Thue-Morse constant
def ThueMorse_Constant(n):
    return tm_poly(QQ(1)/2,n)

# Return a string consisting of the Thue-Morse word
def ThueMorse_Word(n):
    TM = ThueMorse_Compute(n)
    return "".join( [ ('%d' % TM[i]) for i in range(0,n) ] )

# Examples
print ThueMorse_Compute(15)
print ThueMorse_Polynomial(15)
print numerical_approx( ThueMorse_Constant(15) )
print ThueMorse_Word(15)