|
Let's print the first few terms out to check that the string is correct:
[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] |
|
|
[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:
[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.
|
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.
|
How many cube-free strings are there?
[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.
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 |
|