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