A332235 - OEIS

%I #11 Feb 10 2020 06:17:30

%S 2,4,12,47

%N Least integer t such that every binary word of length t+1 contains an split occurrence of an n-overlap.

%C An "n-overlap" is a word of the form xxx', where x is a nonempty word of length at least n, and x' is a prefix of x of length n.  Thus, for example, abcdabcdab is a 2-overlap.  A split occurrence of a pattern p is a word of the form xyz where xz matches the pattern.

%C For n = 0,1,2,3 the lexicographically least words achieving the bound are:

%C n = 0: 01

%C n = 1: 0011

%C n = 2: 000110100111

%C n = 3: 00111010100001010011101000011111000011010001110

%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.

%Y Cf. A332234.

%K nonn,more

%O 0,1

%A _Jeffrey Shallit_, Feb 07 2020