A342263 - OEIS

A342263

a(n) is the length of the longest substring appearing twice (possibly with overlap) in the binary expansion of n.

%I #12 Mar 11 2021 11:41:19

%S 0,0,0,1,1,1,1,2,2,1,2,1,1,1,2,3,3,2,2,1,2,3,2,2,2,1,2,2,2,2,3,4,4,3,

%T 2,2,3,2,2,2,2,2,4,3,2,3,2,3,3,2,2,2,2,3,3,2,2,2,2,2,3,3,4,5,5,4,3,3,

%U 3,2,2,2,3,4,3,2,3,2,2,3,3,2,3,2,4,5,3

%N a(n) is the length of the longest substring appearing twice (possibly with overlap) in the binary expansion of n.

%C We ignore leading zeros, but the duplicate substrings can have leading zeros.

%C This sequence diverges (for any k > 0, a number n with k*(2^k+1) or more binary digits has necessarily a length-k repeated substring in its binary expansion, so a(n) >= k).

%H Rémy Sigrist, <a href="/A342263/b342263.txt">Table of n, a(n) for n = 0..8192</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F a(n) < A070939(n).

%F a(2^k) = a(2^k-1) = k-1 for any k > 0.

%e The first terms, alongside the binary expansion of n and the corresponding longest repeated substrings, are:

%e n a(n) bin(n) longest duplicate substrings

%e -- ---- ------ ----------------------------

%e 0 0 0 ""

%e 1 0 1 ""

%e 2 0 10 ""

%e 3 1 11 "1"

%e 4 1 100 "0"

%e 5 1 101 "1"

%e 6 1 110 "1"

%e 7 2 111 "11"

%e 8 2 1000 "00"

%e 9 1 1001 "0", "1"

%e 10 2 1010 "10"

%e 11 1 1011 "1"

%e 12 1 1100 "0", "1"

%e 13 1 1101 "1"

%e 14 2 1110 "11"

%e 15 3 1111 "111"

%o (PARI) a(n) = { my (b=if (n, binary(n), [0])); for (w=1, oo, my (s=vector(#b+1-w, o, b[o..o+w-1])); if (#s==#Set(s), return (w-1))) }

%o (Python)

%o def a(n):

%o b = bin(n)[2:]

%o for k in range(len(b), -1, -1):

%o for i in range(len(b)-k):

%o for j in range(i+1, len(b)-k+1):

%o if b[i:i+k] == b[j:j+k]: return k

%o print([a(n) for n in range(87)]) # _Michael S. Branicky_, Mar 07 2021

%Y Cf. A070939, A342298.

%K nonn,base

%O 0,8

%A _Rémy Sigrist_, Mar 07 2021