login
In the binary expansion of any nonnegative number n, say with Hamming weight w, reverse the order of the w rightmost bits.
1

%I #17 May 24 2024 13:22:44

%S 0,1,2,3,4,6,5,7,8,10,9,14,12,13,11,15,16,18,17,22,20,21,19,30,24,28,

%T 26,29,25,27,23,31,32,34,33,38,36,37,35,46,40,44,42,45,41,43,39,62,48,

%U 52,50,60,49,58,54,61,56,57,53,59,51,55,47,63,64,66,65,70

%N In the binary expansion of any nonnegative number n, say with Hamming weight w, reverse the order of the w rightmost bits.

%C This sequence is a self-inverse permutation of the nonnegative integers.

%H Rémy Sigrist, <a href="/A373038/b373038.txt">Table of n, a(n) for n = 0..8192</a>

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

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

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

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

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

%e For n = 43: the binary expansion of 43 is "101011", and has Hamming weight 4, reversing the 4 rightmost bits yields "101101", so a(43) = 45.

%o (PARI) a(n) = { my (b = binary(n), w = hammingweight(n)); fromdigits(concat( b[1..#b-w], Vecrev(b[#b-w+1..#b])), 2); }

%o (Python)

%o def a(n): w, b = n.bit_count(), bin(n)[2:]; return int(b[:-w]+b[-w:][::-1], 2)

%o print([a(n) for n in range(68)]) # _Michael S. Branicky_, May 24 2024

%Y Cf. A000120, A059893.

%K nonn,base,easy

%O 0,3

%A _Rémy Sigrist_, May 20 2024