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

Author

Rémy Sigrist, Aug 10 2024

Keywords

• nonn
• base
• look

Comments

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

Examples

			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
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..8190
• Index entries for sequences related to binary expansion of n

Crossrefs

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

Programs

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

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

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