login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A332235 Least integer t such that every binary word of length t+1 contains an split occurrence of an n-overlap. 1
2, 4, 12, 47 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

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.

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

n = 0: 01

n = 1: 0011

n = 2: 000110100111

n = 3: 00111010100001010011101000011111000011010001110

LINKS

Table of n, a(n) for n=0..3.

D. Gabric and J. Shallit, Avoidance of split overlaps, arxiv preprint arXiv:2002.01968 [cs.DM], February 5 2020.

CROSSREFS

Cf. A332234.

Sequence in context: A238111 A165901 A074449 * A131387 A207647 A152453

Adjacent sequences:  A332232 A332233 A332234 * A332236 A332237 A332238

KEYWORD

nonn,more

AUTHOR

Jeffrey Shallit, Feb 07 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 2 08:50 EDT 2020. Contains 335398 sequences. (Running on oeis4.)