cp's OEIS Frontend

A057889 Bijective bit-reverse of n: keep the trailing zeros in the binary expansion of n fixed, but reverse all the digits up to that point.

%I A057889 #57 Dec 25 2024 15:03:06
%S A057889 0,1,2,3,4,5,6,7,8,9,10,13,12,11,14,15,16,17,18,25,20,21,26,29,24,19,
%T A057889 22,27,28,23,30,31,32,33,34,49,36,41,50,57,40,37,42,53,52,45,58,61,48,
%U A057889 35,38,51,44,43,54,59,56,39,46,55,60,47,62,63,64,65,66,97,68,81,98,113
%N A057889 Bijective bit-reverse of n: keep the trailing zeros in the binary expansion of n fixed, but reverse all the digits up to that point.
%C A057889 The original name was "Bit-reverse of n, including as many leading as trailing zeros." - _Antti Karttunen_, Dec 25 2024
%C A057889 A permutation of integers consisting only of fixed points and pairs. a(n)=n when n is a binary palindrome (including as many leading as trailing zeros), otherwise a(n)=A003010(n) (i.e. n has no axis of symmetry). A057890 gives the palindromes (fixed points, akin to A006995) while A057891 gives the "antidromes" (pairs). See also A280505.
%C A057889 This is multiplicative in domain GF(2)[X], i.e. with carryless binary arithmetic. A193231 is another such permutation of natural numbers. - _Antti Karttunen_, Dec 25 2024
%H A057889 N. J. A. Sloane, <a href="/A057889/b057889.txt">Table of n, a(n) for n = 0..16384</a>, May 30 2016 [First 8192 terms from _Ivan Neretin_, Jul 09 2015]
%H A057889 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H A057889 <a href="/index/Ge#GF2X">Index entries for sequences related to polynomials in ring GF(2)[X]</a>
%H A057889 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A057889 a(n) = A030101(A000265(n)) * A006519(n), with a(0)=0.
%e A057889 a(6)=6 because 0110 is a palindrome, but a(11)=13 because 1011 reverses into 1101.
%t A057889 Table[FromDigits[Reverse[IntegerDigits[n, 2]], 2]*2^IntegerExponent[n, 2], {n, 71}] (* _Ivan Neretin_, Jul 09 2015 *)
%o A057889 (Python)
%o A057889 def a(n):
%o A057889     x = bin(n)[2:]
%o A057889     y = x[::-1]
%o A057889     return int(str(int(y))+(len(x) - len(str(int(y))))*'0', 2)
%o A057889 print([a(n) for n in range(101)]) # _Indranil Ghosh_, Jun 11 2017
%o A057889 (Python)
%o A057889 def A057889(n): return int(bin(n>>(m:=(~n&n-1).bit_length()))[-1:1:-1],2)<<m # _Chai Wah Wu_, Dec 25 2024
%o A057889 (PARI)
%o A057889 A030101(n) = if(n<1,0,subst(Polrev(binary(n)),x,2));
%o A057889 A057889(n) = if(!n,n,A030101(n/(2^valuation(n,2))) * (2^valuation(n, 2))); \\ _Antti Karttunen_, Dec 25 2024
%Y A057889 Cf. A030101, A000265, A006519, A006995, A057890, A057891, A280505, A280508, A331166 [= min(n,a(n))], A366378 [k for which a(k) = k (mod 3)], A369044 [= A014963(a(n))].
%Y A057889 Similar permutations for other bases: A263273 (base-3), A264994 (base-4), A264995 (base-5), A264979  (base-9).
%Y A057889 Other related (binary) permutations: A056539, A193231.
%Y A057889 Compositions of this permutation with other binary (or other base-related) permutations: A264965, A264966, A265329, A265369, A379471, A379472.
%Y A057889 Compositions with permutations involving prime factorization: A245450, A245453, A266402, A266404, A293448, A366275, A366276.
%Y A057889 Other derived permutations: A246200 [= a(3*n)/3], A266351, A302027, A302028, A345201, A356331, A356332, A356759, A366389.
%Y A057889 See also A235027 (which is not a permutation).
%K A057889 easy,nonn,base,look
%O A057889 0,3
%A A057889 _Marc LeBrun_, Sep 25 2000
%E A057889 Clarified the name with May 30 2016 comment from _N. J. A. Sloane_, and moved the old name to the comments - _Antti Karttunen_, Dec 25 2024