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
    # add word to answer
    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) }

References