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,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).

Links

Rémy Sigrist, Table of n, a(n) for n = 0..8192

Index entries for sequences related to binary expansion of n

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

Cf. A070939, A342298.

Sequence in context: A218450 A025912 A029441 * A109495 A164295 A035214

Adjacent sequences: A342260 A342261 A342262 * A342264 A342265 A342266

Keyword

nonn,base

Author

Rémy Sigrist, Mar 07 2021

Status

approved