A373886 a(n) is the least number whose binary expansion can be obtained by reversing one or more consecutive bits in the binary expansion of n.

0, 1, 1, 3, 1, 3, 3, 7, 1, 3, 5, 7, 3, 7, 7, 15, 1, 3, 6, 7, 5, 11, 13, 15, 3, 7, 11, 15, 7, 15, 15, 31, 1, 3, 6, 7, 9, 13, 14, 15, 5, 11, 21, 23, 13, 27, 29, 31, 3, 7, 14, 15, 11, 23, 27, 31, 7, 15, 23, 31, 15, 31, 31, 63, 1, 3, 6, 7, 12, 13, 14, 15, 9, 19

Offset

0,4

Comments

This sequence has similarities with A087734; here we reverse some consecutive bits, there we negate some consecutive bits.

Links

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

Index entries for sequences related to binary expansion of n

Formula

a(n) <= n with equality iff n belongs to A000225.

a^k(n) = A038573(n) for k sufficiently large (where a^k denotes the k-th iterate of the sequence).

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

A000120(a(n)) = A000120(n).

Example

The first terms, alongside their binary expansion, are:
  n   a(n)  bin(n)  bin(a(n))
  --  ----  ------  ---------
   0     0       0          0
   1     1       1          1
   2     1      10          1
   3     3      11         11
   4     1     100          1
   5     3     101         11
   6     3     110         11
   7     7     111        111
   8     1    1000          1
   9     3    1001         11
  10     5    1010        101
  11     7    1011        111
  12     3    1100         11
  13     7    1101        111
  14     7    1110        111
  15    15    1111       1111
  16     1   10000          1

Maple

f:= proc(n) local L, nL, i, j, k, r, x;
  L:= convert(n, base, 2);
  nL:= nops(L);
  r:= n;
  for i from 1 to nL-1 do
    for j from i+1 to nL do
      r:= min(r, n + add((L[j-k]-L[i+k])*2^(i+k-1), k=0..j-i));
  od od;
  r
end proc:
map(f, [$0..100]); # Robert Israel, Aug 13 2024

Prog

(PARI) a(n, base = 2) = { my (d = if (n, digits(n, base), [0])); setbinop((i, j) -> fromdigits(concat([d[1..i-1], Vecrev(d[i..j]), d[j+1..#d]]), base), [1..#d])[1]; }
(Python)
def a(n):
    b = bin(n)[2:]
    return min(int(b[:i]+b[i:j][::-1]+b[j:], 2) for i in range(len(b)) for j in range(i, len(b)+1))
print([a(n) for n in range(74)]) # Michael S. Branicky, Aug 13 2024

Crossrefs

Cf. A000120, A000225, A038573, A087734, A331856.

Sequence in context: A355339 A331856 A163381 * A327190 A160123 A238784

Adjacent sequences: A373883 A373884 A373885 * A373887 A373888 A373889

Keyword

nonn,base,look

Author

Rémy Sigrist, Aug 10 2024

Status

approved