A373886 - OEIS

%I #57 Aug 14 2024 11:06:06

%S 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,

%T 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,

%U 31,7,15,23,31,15,31,31,63,1,3,6,7,12,13,14,15,9,19

%N 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.

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

%H Rémy Sigrist, <a href="/A373886/b373886.txt">Table of n, a(n) for n = 0..8190</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

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

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

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

%F A000120(a(n)) = A000120(n).

%e The first terms, alongside their binary expansion, are:

%e   n   a(n)  bin(n)  bin(a(n))

%e   --  ----  ------  ---------

%e    0     0       0          0

%e    1     1       1          1

%e    2     1      10          1

%e    3     3      11         11

%e    4     1     100          1

%e    5     3     101         11

%e    6     3     110         11

%e    7     7     111        111

%e    8     1    1000          1

%e    9     3    1001         11

%e   10     5    1010        101

%e   11     7    1011        111

%e   12     3    1100         11

%e   13     7    1101        111

%e   14     7    1110        111

%e   15    15    1111       1111

%e   16     1   10000          1

%p f:= proc(n) local L,nL,i,j,k,r,x;

%p   L:= convert(n,base,2);

%p   nL:= nops(L);

%p   r:= n;

%p   for i from 1 to nL-1 do

%p     for j from i+1 to nL do

%p       r:= min(r, n + add((L[j-k]-L[i+k])*2^(i+k-1),k=0..j-i));

%p   od od;

%p   r

%p end proc:

%p map(f, [$0..100]); # _Robert Israel_, Aug 13 2024

%o (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]; }

%o (Python)

%o def a(n):

%o     b = bin(n)[2:]

%o     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))

%o print([a(n) for n in range(74)]) # _Michael S. Branicky_, Aug 13 2024

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

%K nonn,base,look

%O 0,4

%A _Rémy Sigrist_, Aug 10 2024