# Word repetitions

Find a sequence of binary symbols where no word of size 4 is found in two places ...

``````0000 1111 0101 1001 000

0000 - 0
0001 - 1
0011 - 3
0111 - 7
1111 - 15
1110 - 14
1101 - 13
1010 - 10
0101 - 5
1011 - 11
0110 - 6
1100 - 12
1001 - 9
0010 - 2
0100 - 4
1000 - 8
``````

## Using Lyndon words

"Concatenating together, in lexicographic order, all the Lyndon words whose length divides n".

For example L(k,n) = L(2,4)

Lyndon words.

``````0, 1, 01, 001, 011, 0001, 0011, 0111, 00001, 00011, 00101, 00111, 01011, 01111, ...
``````

Select works with length that divides 4 i.e. 1, 2 and 4.

``````0, 1, 01, 0001, 0011, 0111
``````

Sort in lexicographic order. Add zeroes to the end if necessary in comparison.

``````0, 0001, 0011, 01, 0111, 1
``````

Concatenate. Use symbols from beginning in the end.

``````0 0001 0011 01 0111 1

0000 1001 1010 1111 000

0000100110101111 000

0000 = 0
0001 = 1
0010 = 2
0100 = 4
1001 = 9
0011 = 3
0110 = 6
1101 = 13
1010 = 10
0101 = 5
1011 = 11
0111 = 7
1111 = 15
1110 = 14
1100 = 12
1000 = 8
``````

## Generate Lyndon words

``````#!/usr/local/bin/ruby

# Generate Lyndon words with number of symbols s <= 10 of max size n
def LengthLimitedLyndonWords(s,n)
ans = []
w = [-1]
while w.size > 0 do
# increment the last non-z symbol
w[-1] += 1
ans << w.join
m = w.size
# repeat word to fill exactly n syms
while w.size < n do
w << w[-m]
end
# delete last symbol if max
while w.size > 0 and w[-1] == s - 1 do
w.pop
end
end
return ans
end

# sort on size and then on lexically
def LyndonWordsOrder(n,w)
(10**n)*w.size + w.to_i
end

# Generate wikipedia sequence: <https://en.wikipedia.org/wiki/Lyndon_word>
words = LengthLimitedLyndonWords(2,5)
puts words.sort_by{ |w| LyndonWordsOrder(5,w) }
``````