2021.08.30 MATH 3600 Thue Morse Sequence

93 days ago by calkin

Recall from last class: the Thue-Morse sequence is a 01 sequence defined as follows.

$0$

If at any stage we have a sequence $S=\sigma_0 \sigma_1 \dots \sigma_k$ then we construct our new sequence as $\sigma_0 \sigma_1 \dots \sigma_k$ followed by $\bar{\sigma}_0 \bar{\sigma}_1 \dots \bar{\sigma}_k$, that is

$S \bar{S}= \sigma_0 \sigma_1 \dots \sigma_k \bar{\sigma}_0 \bar{\sigma}_1 \dots \bar{\sigma}_k$

in which $\bar{0}=1$ and $\bar{1}=0$ denotes the binary complement.

How should we code this?  Let's start with a list for $S$, and a list for $\bar{S}$: we'll use variables S and Sbar.

S=[0] Sbar=[1]

At each stage, we'll construct the new sequences T and barT from S and Sbar, and then obtain the new S and Sbar from them.

T=S+Sbar Tbar=Sbar + S
print(T,Tbar)
 ([0, 1], [1, 0]) ([0, 1], [1, 0])
S=T Sbar=Tbar
print(S,Sbar)
 ([0, 1], [1, 0]) ([0, 1], [1, 0])
T=S+Sbar Tbar=Sbar + S
print(T,Tbar)
 ([0, 1, 1, 0], [1, 0, 0, 1]) ([0, 1, 1, 0], [1, 0, 0, 1])
S=T Sbar=Tbar
N= 10 # the number of iterations we wish to perform S=[0] Sbar=[1] for i in srange(N): T=S+Sbar Tbar=Sbar+S S=T Sbar=Tbar #print(S) #print(len(S))

This code appears to work!

After $N$ iterations, how many entries will $S$ have?  $2^N$ entries!

S[1001]
 1 1
def f(): print("Hello world") # This function doesn't take any input or return any value!
f()
 Hello world Hello world
a=f()
 Hello world Hello world
print(a) print(type(a))
 None  None 
def f(n): return(n+1) # f takes an integer entry and return the input plus 1.
f(10)
 11 11
f(1/2)
 3/2 3/2

Functions!

A function $f(x)$ is a construct which takes an input $x$ (which may consist of one or more values, or even none!)

def f(n): if n.is_integer(): return(n+1) else: return('Do make sure that n is an integer')
N.is_integer()
 True True
f(10)
 11 11
f(3/2)
 'Do make sure that n is an integer' 'Do make sure that n is an integer'
def TM(n): # Return the first 2^n entries of the Thue-Morse sequence if n.is_integer() and n >=0: S=[0] Sbar=[1] for i in srange(n): T=S+Sbar Tbar=Sbar+S S=T Sbar=Tbar return(S) else: return('Please make sure input is a non-negative integer')
TM(-1)
 'Please make sure input is a non-negative integer' 'Please make sure input is a non-negative integer'