A332232 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

A332232

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

3

2, 7, 16, 32, 59, 110

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

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.

LINKS

Table of n, a(n) for n=1..6.

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

EXAMPLE

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

1: 01

2: 0001110

3: 0000010101111100

4: 01010100100110110111111100000001

5: 00000000010001000110011001110100101010101101101111111110000

6: 0000000000010000100001100011000111001110011110100010100\

1010010110010011011011010101010111011101111111111100000

CROSSREFS

Sequence in context: A216499 A228189 A023550 * A333395 A130869 A212576

Adjacent sequences: A332229 A332230 A332231 * A332233 A332234 A332235

KEYWORD

nonn,more

AUTHOR

Jeffrey Shallit, Feb 07 2020

EXTENSIONS

a(6) from Bert Dobbelaere, Feb 08 2020

STATUS

approved