A342263 a(n) is the length of the longest substring appearing twice (possibly with overlap) in the binary expansion of n.
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, 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, 3, 2, 2, 2, 3, 4, 3, 2, 3, 2, 2, 3, 3, 2, 3, 2, 4, 5, 3
Offset: 0
Examples
The first terms, alongside the binary expansion of n and the corresponding longest repeated substrings, are: n a(n) bin(n) longest duplicate substrings -- ---- ------ ---------------------------- 0 0 0 "" 1 0 1 "" 2 0 10 "" 3 1 11 "1" 4 1 100 "0" 5 1 101 "1" 6 1 110 "1" 7 2 111 "11" 8 2 1000 "00" 9 1 1001 "0", "1" 10 2 1010 "10" 11 1 1011 "1" 12 1 1100 "0", "1" 13 1 1101 "1" 14 2 1110 "11" 15 3 1111 "111"
Links
Programs
-
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))) } -
Python
def a(n): b = bin(n)[2:] for k in range(len(b), -1, -1): for i in range(len(b)-k): for j in range(i+1, len(b)-k+1): if b[i:i+k] == b[j:j+k]: return k print([a(n) for n in range(87)]) # Michael S. Branicky, Mar 07 2021
Formula
a(n) < A070939(n).
a(2^k) = a(2^k-1) = k-1 for any k > 0.
Comments