cp's OEIS Frontend

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

%I A080261 #21 Sep 20 2022 07:52:50
%S A080261 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,
%T A080261 25,24,31,30,29,28,39,38,37,36,35,34,33,32,47,46,45,44,43,42,41,40,55,
%U A080261 54,53,52,51,50,49,48,63,62,61,60,59,58,57,56,71,70,69,68,67,66,65,64,79
%N A080261 Simple involution of natural numbers: complement [binary_width(n)/2] least significant bits in the binary expansion of n.
%H A080261 N. J. A. Sloane, <a href="/transforms.txt">Maple implementation of bitwise AND (ANDnos)</a>
%H A080261 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e A080261 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.
%p A080261 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;
%p A080261 binwidth := n -> (`if`((0 = n),1,floor_log_2(n)+1));
%p A080261 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;
%t A080261 A080261[n_] := With[{w = Floor[binwidth[n]/2]}, 2^w* Floor[n/2^w] + ((2^w) - 1) - BitAnd[n, 2^w - 1]];
%t A080261 binwidth [n_] :=  If[0 == n, 1, floorLog2[n] + 1];
%t A080261 floorLog2[n_] := Module[{nn = n, i}, For[i = -1, i <= n, i++, If[0 == nn, Return[i]]; nn = Floor[nn/2]]];
%t A080261 Table[A080261[n], {n, 0, 100}] (* _Jean-François Alcover_, Sep 20 2022, after Maple program *)
%o A080261 (Sage)
%o A080261 def A080261(n) :
%o A080261     w = (2*n).exact_log(2) if n != 0 else 1
%o A080261     w2 = 1 << w//2
%o A080261     return w2*(n//w2) + w2 - 1 - (n&(w2-1))
%o A080261 [A080261(n) for n in (0..72)] # _Peter Luschny_, Aug 08 2012
%o A080261 (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
%Y A080261 Used to construct A080117.
%K A080261 nonn
%O A080261 0,3
%A A080261 _Antti Karttunen_, Feb 11 2003