A284248 - OEIS

%I #12 Dec 08 2023 07:11:23

%S 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,

%T 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,

%U 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

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

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

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

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

%o (PARI) a(n) = my(j=logint(n,2)); j - (j > n-1<<j); \\ _Kevin Ryde_, Dec 08 2023

%o (Python)

%o def a(n): j = len(bin(n)[2:])-1; return j - (j > n - (1<<j))

%o print([a(n) for n in range(1, 131)]) # _Michael S. Branicky_, Dec 08 2023 after _Kevin Ryde_

%K nonn,easy

%O 1,6

%A _Jeffrey Shallit_, Mar 23 2017