login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A342263 a(n) is the length of the longest substring appearing twice (possibly with overlap) in the binary expansion of n. 2
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 27 08:39 EDT 2021. Contains 347689 sequences. (Running on oeis4.)