cp's OEIS Frontend

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

%I A342263 #12 Mar 11 2021 11:41:19
%S A342263 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 A342263 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 A342263 3,2,2,2,3,4,3,2,3,2,2,3,3,2,3,2,4,5,3
%N A342263 a(n) is the length of the longest substring appearing twice (possibly with overlap) in the binary expansion of n.
%C A342263 We ignore leading zeros, but the duplicate substrings can have leading zeros.
%C A342263 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 A342263 Rémy Sigrist, <a href="/A342263/b342263.txt">Table of n, a(n) for n = 0..8192</a>
%H A342263 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A342263 a(n) < A070939(n).
%F A342263 a(2^k) = a(2^k-1) = k-1 for any k > 0.
%e A342263 The first terms, alongside the binary expansion of n and the corresponding longest repeated substrings, are:
%e A342263   n   a(n)  bin(n)  longest duplicate substrings
%e A342263   --  ----  ------  ----------------------------
%e A342263    0     0       0  ""
%e A342263    1     0       1  ""
%e A342263    2     0      10  ""
%e A342263    3     1      11  "1"
%e A342263    4     1     100  "0"
%e A342263    5     1     101  "1"
%e A342263    6     1     110  "1"
%e A342263    7     2     111  "11"
%e A342263    8     2    1000  "00"
%e A342263    9     1    1001  "0", "1"
%e A342263   10     2    1010  "10"
%e A342263   11     1    1011  "1"
%e A342263   12     1    1100  "0", "1"
%e A342263   13     1    1101  "1"
%e A342263   14     2    1110  "11"
%e A342263   15     3    1111  "111"
%o A342263 (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 A342263 (Python)
%o A342263 def a(n):
%o A342263   b = bin(n)[2:]
%o A342263   for k in range(len(b), -1, -1):
%o A342263     for i in range(len(b)-k):
%o A342263       for j in range(i+1, len(b)-k+1):
%o A342263         if b[i:i+k] == b[j:j+k]: return k
%o A342263 print([a(n) for n in range(87)]) # _Michael S. Branicky_, Mar 07 2021
%Y A342263 Cf. A070939, A342298.
%K A342263 nonn,base
%O A342263 0,8
%A A342263 _Rémy Sigrist_, Mar 07 2021