kolakoski_2011_09_19

3667 days ago by calkin

kolakoski=[0,1,2,2] readi=3 writei=4 current=1 while writei<=2^10+4: kolakoski.append(current) if kolakoski[readi]==2: kolakoski.append(current) writei=writei+1 writei=writei+1 readi=readi+1 #current=swapit(current) current=3-current #this changes the current character from 1 to 2 and vice versa. 
       

Let's print the first few terms out to check that the string is correct:
[kolakoski[i] for i in range(1,20)] 
        
[1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2]
[1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2]
k=5 
       
occurrences=[0 for i in range(2^k)] 
       
i = 1 while i+k<=len(kolakoski): #substring=16*(kolakoski[i]%2)+8*(kolakoski[i+1]%2)+4*(kolakoski[i+2]%2)+2*(kolakoski[i+3]%2)+(kolakoski[i+4]%2) substring=0 for j in range(k): substring += (kolakoski[i+j]%2)*2^(k-j-1) i=i+1 occurrences[substring]=occurrences[substring]+1 print occurrences 2^k-occurrences.count(0) 
        
[0, 0, 0, 0, 55, 55, 60, 0, 0, 114, 0, 55, 55, 117, 0, 0, 0, 0, 110, 60,
59, 0, 112, 0, 0, 55, 59, 58, 0, 0, 0, 0]
14
[0, 0, 0, 0, 55, 55, 60, 0, 0, 114, 0, 55, 55, 117, 0, 0, 0, 0, 110, 60, 59, 0, 112, 0, 0, 55, 59, 58, 0, 0, 0, 0]
14

Let's see how things behave for length 6: 
k=6 occurrences=[0 for i in range(2^k)] while i+k<=len(kolakoski): #substring=16*(kolakoski[i]%2)+8*(kolakoski[i+1]%2)+4*(kolakoski[i+2]%2)+2*(kolakoski[i+3]%2)+(kolakoski[i+4]%2) substring=0 for j in range(k): substring += (kolakoski[i+j]%2)*2^(k-j-1) i=i+1 occurrences[substring]=occurrences[substring]+1 print occurrences 2^k-occurrences.count(0) 
        
[0, 0, 0, 0, 0, 0, 0, 0, 0, 51, 0, 53, 0, 55, 0, 0, 0, 0, 51, 55, 0, 0,
52, 0, 0, 53, 54, 55, 0, 0, 0, 0, 0, 0, 0, 0, 51, 53, 55, 0, 0, 54, 0,
0, 53, 54, 0, 0, 0, 0, 53, 0, 54, 0, 55, 0, 0, 0, 0, 0, 0, 0, 0, 0]
18
[0, 0, 0, 0, 0, 0, 0, 0, 0, 51, 0, 53, 0, 55, 0, 0, 0, 0, 51, 55, 0, 0, 52, 0, 0, 53, 54, 55, 0, 0, 0, 0, 0, 0, 0, 0, 51, 53, 55, 0, 0, 54, 0, 0, 53, 54, 0, 0, 0, 0, 53, 0, 54, 0, 55, 0, 0, 0, 0, 0, 0, 0, 0, 0]
18

How many binary cube-free strings are there of length $k$?

Suppose we've constructed all cube-free strings of length $k$: then we can construct all cube-free strings of length $k+1$, by just testing whether the addition of 0, respectively a 1, creates a cube.  The following function returns False if the string has a cube terminating the string, and True otherwise.
def iscubefree(str): n=len(str) l=1 cf=True while 3*l<=n and cf==True: i=0 iscube=True while i<l and iscube==True: if ((str[n-1-i]==str[n-1-i-l]) and (str[n-1-i]==str[n-1-i-2*l]))==False: iscube=False i=i+1 if iscube==True: cf=False l=l+1 return(cf) 
       
print iscubefree([1,1,1]) print iscubefree([1,1,1,0]) print iscubefree([0,1,1,1]) print iscubefree([0,0,1,0,1,0,1]) print iscubefree([0,0,1,0,1,0,1,1]) 
        
False
True
False
False
True
False
True
False
False
True

Note that it is only checking whether the strings are terminated by a cube!

Now, list all cube-free strings of length 1, and of length 2, and obtain all cube-free strings of length up to 6.
cfs=[[[0],[1]],[[0,0],[0,1],[1,0],[1,1]]] j=2 while j<7: n= len(cfs) nextstring=[] #print n for str in cfs[n-1]: localstr=str[0:len(str)] localstr.append(0) #print str,localstr if iscubefree(localstr): nextstring.append(localstr) localstr=str[0:len(str)] localstr.append(1) #print str,localstr if iscubefree(localstr): nextstring.append(localstr) cfs.append(nextstring) j=j+1 
       

How many cube-free strings are there? 
map(len, cfs) 
        
[2, 4, 6, 10, 16, 24, 36]
[2, 4, 6, 10, 16, 24, 36]

We see that there are 24 cube-free strings of length 5, but only 14 occur in kolakoski,

and 36 of length 6, only 18 of which occur in kolakoski.
for i in srange(32) : print i.binary(),occurrences[i] 
        
0 0
1 0
10 0
11 0
100 0
101 0
110 0
111 0
1000 0
1001 51
1010 0
1011 53
1100 0
1101 55
1110 0
1111 0
10000 0
10001 0
10010 51
10011 55
10100 0
10101 0
10110 52
10111 0
11000 0
11001 53
11010 54
11011 55
11100 0
11101 0
11110 0
11111 0
0 0
1 0
10 0
11 0
100 0
101 0
110 0
111 0
1000 0
1001 51
1010 0
1011 53
1100 0
1101 55
1110 0
1111 0
10000 0
10001 0
10010 51
10011 55
10100 0
10101 0
10110 52
10111 0
11000 0
11001 53
11010 54
11011 55
11100 0
11101 0
11110 0
11111 0