A284248 Every binary string w of length n has a subword of length a(n) that appears at least twice in w.

0, 0, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6

Offset

1,6

Comments

Here by "subword" we mean a contiguous block that appears inside w.

Links

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

Formula

If 2^j + j <= n <= 2^{j+1} + j then a(n) = j.

Example

For n = 6 every binary string of length >= 6 has a length-2 subword that appears at least twice. So a(6) = 2.

Prog

(PARI) a(n) = my(j=logint(n, 2)); j - (j > n-1<<j); \\ Kevin Ryde, Dec 08 2023
(Python)
def a(n): j = len(bin(n)[2:])-1; return j - (j > n - (1<<j))
print([a(n) for n in range(1, 131)]) # Michael S. Branicky, Dec 08 2023 after Kevin Ryde

Crossrefs

Sequence in context: A068549 A132173 A023968 * A204166 A227581 A263846

Adjacent sequences: A284245 A284246 A284247 * A284249 A284250 A284251

Keyword

nonn,easy

Author

Jeffrey Shallit, Mar 23 2017

Status

approved