login
A342263
a(n) is the length of the longest substring appearing twice (possibly with overlap) in the binary expansion of n.
4
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,8
COMMENTS
We ignore leading zeros, but the duplicate substrings can have leading zeros.
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).
FORMULA
a(n) < A070939(n).
a(2^k) = a(2^k-1) = k-1 for any k > 0.
EXAMPLE
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"
PROG
(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
CROSSREFS
Sequence in context: A218450 A025912 A029441 * A109495 A164295 A035214
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Mar 07 2021
STATUS
approved