A080261 Simple involution of natural numbers: complement [binary_width(n)/2] least significant bits in the binary expansion of n.

0, 1, 3, 2, 5, 4, 7, 6, 11, 10, 9, 8, 15, 14, 13, 12, 19, 18, 17, 16, 23, 22, 21, 20, 27, 26, 25, 24, 31, 30, 29, 28, 39, 38, 37, 36, 35, 34, 33, 32, 47, 46, 45, 44, 43, 42, 41, 40, 55, 54, 53, 52, 51, 50, 49, 48, 63, 62, 61, 60, 59, 58, 57, 56, 71, 70, 69, 68, 67, 66, 65, 64, 79

Offset: 0

Author

Antti Karttunen, Feb 11 2003

Keywords

• nonn

Examples

			Binary expansion of 9 is 1001, we complement 4/2 = two rightmost bits, yielding 1010 = 10, thus a(9)=10. Binary expansion of 20 is 10100, we complement [5/2] = 2 rightmost bits, giving 10111 = 23, thus a(20)=23.
		

Links

• N. J. A. Sloane, Maple implementation of bitwise AND (ANDnos)
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Used to construct A080117.

Programs

Maple

A080261 := proc(n) local w; w := floor(binwidth(n)/2); RETURN(((2^w)*floor(n/(2^w)))+(((2^w)-1)-ANDnos(n,(2^w)-1))); end;
binwidth := n -> (`if`((0 = n),1,floor_log_2(n)+1));
floor_log_2 := proc(n) local nn,i; nn := n; for i from -1 to n do if(0 = nn) then RETURN(i); fi; nn := floor(nn/2); od; end;

Mathematica

A080261[n_] := With[{w = Floor[binwidth[n]/2]}, 2^w* Floor[n/2^w] + ((2^w) - 1) - BitAnd[n, 2^w - 1]];
binwidth [n_] :=  If[0 == n, 1, floorLog2[n] + 1];
floorLog2[n_] := Module[{nn = n, i}, For[i = -1, i <= n, i++, If[0 == nn, Return[i]]; nn = Floor[nn/2]]];
Table[A080261[n], {n, 0, 100}] (* Jean-François Alcover, Sep 20 2022, after Maple program *)

PARI

a(n) = my(b=binary(n), k); if (#b%2, k=#b\2+2, k=#b/2+1); for (i=k, #b, b[i]=1-b[i]); fromdigits(b, 2); \\ Michel Marcus, Sep 20 2022

Sage

def A080261(n) :
    w = (2*n).exact_log(2) if n != 0 else 1
    w2 = 1 << w//2
    return w2*(n//w2) + w2 - 1 - (n&(w2-1))
[A080261(n) for n in (0..72)] # Peter Luschny, Aug 08 2012