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,3

Links

Table of n, a(n) for n=0..72.

N. J. A. Sloane, Maple implementation of bitwise AND (ANDnos)

Index entries for sequences that are permutations of the natural numbers

Example

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.

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

Prog

(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
(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

Crossrefs

Used to construct A080117.

Sequence in context: A093714 A353904 A353780 * A138310 A270197 A332769

Adjacent sequences: A080258 A080259 A080260 * A080262 A080263 A080264

Keyword

nonn

Author

Antti Karttunen, Feb 11 2003

Status

approved