login
Smallest t such that every binary word of length t+1 contains two non-overlapping occurrences of some length-n block.
3

%I #17 Feb 09 2020 02:53:29

%S 2,7,16,32,59,110

%N Smallest t such that every binary word of length t+1 contains two non-overlapping occurrences of some length-n block.

%C If instead we allow overlapping occurrences, then the bound is k^n + n - 1 and is achieved for all k, n >= 1 through de Bruijn sequences.

%H D. Gabric and J. Shallit, <a href="https://arxiv.org/abs/2002.01968">Avoidance of split overlaps</a>, arxiv preprint arXiv:2002.01968 [cs.DM], February 5 2020.

%e For n = 1..6 the lexicographically least strings of length a(n) are

%e 1: 01

%e 2: 0001110

%e 3: 0000010101111100

%e 4: 01010100100110110111111100000001

%e 5: 00000000010001000110011001110100101010101101101111111110000

%e 6: 0000000000010000100001100011000111001110011110100010100\

%e 1010010110010011011011010101010111011101111111111100000

%Y Cf. A332234.

%K nonn,more

%O 1,1

%A _Jeffrey Shallit_, Feb 07 2020

%E a(6) from _Bert Dobbelaere_, Feb 08 2020