A331803 a(n) is the largest positive integer occurring, when written in binary, as a substring in both binary n and binary n+1.

0, 1, 1, 1, 2, 2, 3, 1, 4, 2, 5, 3, 6, 6, 7, 1, 8, 4, 9, 4, 10, 5, 11, 3, 12, 6, 13, 6, 14, 14, 15, 1, 16, 8, 17, 4, 18, 9, 19, 4, 20, 10, 21, 11, 22, 11, 23, 3, 24, 12, 25, 6, 26, 13, 27, 7, 28, 14, 29, 14, 30, 30, 31, 1, 32, 16, 33, 8, 34, 17, 35, 8, 36, 18

Offset

0,5

Comments

We set a(0) = 0 by convention.

Links

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

Formula

a(n) = A175466(n, n+1) for any n > 0.

a(2*n) = n.

a(2^k-1) = 1 for any k > 0.

Example

The first terms, alongside the binary representations of n, n+1 and a(n), are:
  n   a(n)  bin(n)  bin(n+1)  bin(a(n))
  --  ----  ------  --------  ---------
   0     0       0         1          0
   1     1       1        10          1
   2     1      10        11          1
   3     1      11       100          1
   4     2     100       101         10
   5     2     101       110         10
   6     3     110       111         11
   7     1     111      1000          1
   8     4    1000      1001        100
   9     2    1001      1010         10
  10     5    1010      1011        101

Prog

(PARI) sub(n) = { my (b=binary(n), s=[0]); for (i=1, #b, if (b[i], for (j=i, #b, s=setunion(s, Set(fromdigits(b[i..j], 2)))))); return (s) }
a(n) = my (i=setintersect(sub(n), sub(n+1))); i[#i]

Crossrefs

Cf. A175466.

Sequence in context: A294618 A207507 A278537 * A325184 A353931 A354871

Adjacent sequences: A331800 A331801 A331802 * A331804 A331805 A331806

Keyword

nonn,base

Author

Rémy Sigrist, Jan 26 2020

Status

approved