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.  

We start with the sequence 

\[ 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
<type 'NoneType'>
None
<type 'NoneType'>
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'