2015.10.21 Notes

2227 days ago by krsteph

Kylie Stephens

MATH 3600

C10726950

Making lists of square-free sequences over [0,1,2].

Given a list of such sequences of length k, test each to see if you can prepend 0, 1, then 2.

Ex. Length 1   [[0],[1],[2]]

[0]    Cannot prepend 0

[1]    Can prepend 0    [[0,1],[0,2],[1,0],[1,2]]

[2]    Can prepend 0    [[2,0],[2,1]]

 

Prepend 1?          Prepend 2?

   [0] YES              [0] YES

   [1] NO               [1] YES

   [2] YES              [2] NO

   So, we have [[[0],[1],[2]],[[0,1],[0,2],[1,0],[1,2],[2,0],[2,1]]]

How to test whether we can prepend 0:

Suppose our current word has length $k$,

$\sigma_1$,$\sigma_2$,...,$\sigma_k$

Test whether

0,$\sigma_1$,$\sigma_2$,...,$\sigma_k$

is square-free. For each $j$ so that 2$j$ $\leq$ $k$ + 1,

check whether 

0,$\sigma_1$,$\sigma_2$,...,$\sigma_{j-1}$

and 

0,$\sigma_j$,$\sigma_{j+1}$,...,$\sigma_{2j-1}$

are identitcal words.

are_same(S[0:j],S[j:2j])

Write a function to test if two lists are the same.

 

def are_same($S$,$T$):

if len($S$) = 6$n$($T$):

for $j$ in range (len($S$)):

if $S$[$j$] != $T$[$j$]:

return(False)

else:

return(True)

else:

return(False)

def f(n): if n < 10: return (2*n) return(10^10) 
       
f(9) 
       
18
18
f(10) 
       
10000000000
10000000000
S = srange(20) print S[0:10],S[10:20] 
       
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Cube-free over [0,1]?

Only need to check prepending 0 or 1.

Now, we need to check each word of length $j$, where 3$j \leq k$ +1.

Check whether

$S$[0,$j$] and $S$[$j$,2*$j$]

are the same, and if

$S$[0,$j$] and $S$[2*$j$,3*$j$]

are the same.

if are_same($S$[0,$j$],$S$[$j$,2*$j$]) and are_same($S$[0,$j$],$S$[2*$j$,3*$j$]):

Project:

Code to compute lists of square-free words of length up to and including $n$.

Should return a list of lists of lists.

Show result for length $\leq$ 5.

How far can you compute it?

How fast does the number of square-free words grow?

Plot this.

How many square-free words of length 3 over alphabet with $k$ letters?  $k$($k$-1)$^2$

We'll define a dictionary to help us count, rather than a list.

A dictionary is like a list, except that instead of being indexed by 0,1,2,...,$k$-1, it can be indexed by objects.

d = { 'Professor': 'Calkin', 'Subject': 'Math', 'Course':3600} 
       
type(d) 
       
<type 'dict'>
<type 'dict'>
d['Professor'] 
       
'Calkin'
'Calkin'
d['Subject'] 
       
'Math'
'Math'
d['Course'] 
       
3600
3600
print d 
       
{'Course': 3600, 'Professor': 'Calkin', 'Subject': 'Math'}
{'Course': 3600, 'Professor': 'Calkin', 'Subject': 'Math'}
d.keys() #lists things you can use as an index 
       
['Course', 'Professor', 'Subject']
['Course', 'Professor', 'Subject']
d.values() #lists things you can use an an answer 
       
[3600, 'Calkin', 'Math']
[3600, 'Calkin', 'Math']
d.has_key('Subjects') #asks if it has a certain key 
       
False
False
d.items() #list of two tuples each with what you put in 
       
[('Course', 3600), ('Professor', 'Calkin'), ('Subject', 'Math')]
[('Course', 3600), ('Professor', 'Calkin'), ('Subject', 'Math')]
d['Subject'] = 'Maths' 
       
       
{'Course': 3600, 'Professor': 'Calkin', 'Subject': 'Maths'}
{'Course': 3600, 'Professor': 'Calkin', 'Subject': 'Maths'}
d['Course']+=10 
       
       
{'Course': 3610, 'Professor': 'Calkin', 'Subject': 'Maths'}
{'Course': 3610, 'Professor': 'Calkin', 'Subject': 'Maths'}