Skip to main content
1 of 2
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

I wrote a recursive program to find the words of each length with no cube, avoiding a given string. If I programmed correctly, there are only $230800$ cube-free binary words of length $30$.

$001$: The longest string is of length $17$:

11010110101101100

$010$: The longest $2$ are of length $23$, the one found by Zack Wolske and it's reversal:

10011011001101100110011
11001100110110011011001

The others are equivalent to $000$ (no extra restriction), $001$, or $010$. So, any cube-free binary word of length $24$ or longer has all possible subwords of length $3$.


That was easy, so I'll do the same for words of length $4$, too:

$0010$: There are $76604$ cube-free binary words of length $40$ avoiding $0010$, and I would guess that the entropy per digit is positive, that there is some $a \gt 0, c\gt 1$ so that there are about $a c^n$ cube-free binary strings of length $n$ which avoid $0010$.

$0011$: There are $94238$ cube-free binary words of length $40$ avoiding $0011$.

$0101$: There are $110378$ cube-free binary words of length $40$ avoiding $0101$.

$0110$: The longest $3$ are length $17$. Avoiding $0110$ is not much different from avoiding $011$.

00101001010010011
11001001010010011
11001001010010100
Douglas Zare
  • 28k
  • 6
  • 90
  • 130