A324149 Least integer x such that every set of the length-n subwords of some binary word y is achievable by taking the subwords of some word of length <= x.

2, 5, 10, 24, 77

Offset

1,1

Comments

Another way to say this is that a(n) is the least integer x such that every subset of vertices encountered by some walk on the de Bruijn graph of order n is achievable by a walk of length <= x-n (length = number of edges).

The original definition was: "Maximal length of the shortest non-circular witness over all representable sets of binary vectors of length n.".

Links

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

Shuo Tan and Jeffrey Shallit, Sets represented as the length-n factors of a word, preprint, arXiv:1304.3666 [cs.FL], 2013.

Example

For n = 1,2,3,4 examples of a longest word (whose set of length-n subwords did not appear as the subwords of any shorter word) are 01, 00110, 0001011100, 000010010101100101101111.

Crossrefs

Cf. A324146, A324147, A324148, A375994.

Sequence in context: A253013 A192471 A001431 * A054866 A242935 A109616

Adjacent sequences: A324146 A324147 A324148 * A324150 A324151 A324152

Keyword

nonn,more

Author

N. J. A. Sloane, Feb 26 2019

Extensions

Updated by Jeffrey Shallit, Sep 05 2024; edited by N. J. A. Sloane, Nov 03 2024

Status

approved