login
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.
1
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.
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
KEYWORD
nonn,base,look
AUTHOR
Rémy Sigrist, Aug 10 2024
STATUS
approved