login
A284248
Every binary string w of length n has a subword of length a(n) that appears at least twice in w.
1
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.
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
KEYWORD
nonn,easy
AUTHOR
Jeffrey Shallit, Mar 23 2017
STATUS
approved