We will consider some binary and related sequences.
1. The ThueMorse sequence.
2. The Kolakoski sequence.
The ThueMorse sequence can be defined in several different ways.
(i) Start with 0.
Find the current sequence's binary complement and append it to the current sequence.
0 > 01 > 0110 > 01101001 > 0110100110010110
(ii) second construction: Start with 0
replace every occurence of 0 with 01, every occurence of 1 with 10.
We end up with the same sequence!
(iii) Third construction. List the nonnegative integers in binary, and count the number of 1's (mod 2).
0 > 0
1 > 1
10 > 1
11 > 0
100> 1
101 > 0
110 > 0
111 > 1
What is special about the ThueMorse sequence? Do we ever see three consecutive 0's? Or 1's?
Suppose we did: ask the question: where does the first string of three consecutive 0's or 1's occur?
The three consecutive bits would have to cross a $2^n$ boundary, but since we always have two different consecutive bits at the boundary, this can't happen! So, we never see three consecutive 0's or three consecutive 1's.
Similarly for each of the "words" w of length 2, we can never see three repeated w's. Clearly can't see (00)(00)(00) or (11)(11)(11) or (01)(01)(01) or (10)(10)(10). In fact, it is a theorem that for any word w of length k, we never see three consecutive copies of w. We call the sequence "cubefree".
Can we check this computationally?
Tasks:
(i) Compute the first $2^k$ terms of the ThueMorse sequence
(ii) Write code to check if a sequence has cubes. Read a substring of a sequence and check whether that substring is a cube.
Separate question: given a binary sequence $\Sigma$, which words appear as a consecutive string in the sequence? In the ThueMorse sequence, of the 16 possible binary words of length 4, only 0010, 0011, 0100, 0101, 0110, 1001, 1010, 1011, 1100, 1101, for a total of 10 words that appear.
Task: how many cubefree words of length $j$ are there?
Can you compute them?
What proportion of cubefree words appear as substrings of the ThueMorse sequence? Do they all appear or are there some that are missing?

A puzzle: what is going on with the following sequence?
1
11
21
1211
111221
312211
13112221
1113213211
....


Testing whether a string is cubefree.
Need a function is_a_cube(L), which takes a list L as input, checks that its length is a multiple of 3, and checks whether L is a cube.
Need a function is_cube_free(S), which takes a list, and checks for every j, l with j+3l $\leq$ n if the string
S[j: j+3*l] is a cube. If it ever is, is_cube_free(S) returns False, otherwise it returns True.
You should run your function on the Thue Morse sequence and the Kolakoski sequence to check that they are both cubefree. Also create some noncubefree sequences and check that it tells you they are not cubefree.
It might be helpful as well to have the function print out or return the position and length of a cube found, and perhaps to print out the string which is cubed.
