# 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   [,,]

    Cannot prepend 0

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

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

Prepend 1?          Prepend 2?

 YES               YES

 NO                YES

 YES               NO

So, we have [[,,],[[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)
  
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'}