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.

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, 22, 27, 28, 23, 30, 31, 32, 33, 34, 49, 36, 41, 50, 57, 40, 37, 42, 53, 52, 45, 58, 61, 48, 35, 38, 51, 44, 43, 54, 59, 56, 39, 46, 55, 60, 47, 62, 63, 64, 65, 66, 97, 68, 81, 98, 113

Offset: 0

Author

Marc LeBrun, Sep 25 2000

Keywords

• easy
• nonn
• base
• look

Comments

The original name was "Bit-reverse of n, including as many leading as trailing zeros." - Antti Karttunen, Dec 25 2024

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.

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

Examples

			a(6)=6 because 0110 is a palindrome, but a(11)=13 because 1011 reverses into 1101.
		

Links

• N. J. A. Sloane, Table of n, a(n) for n = 0..16384, May 30 2016 [First 8192 terms from _Ivan Neretin_, Jul 09 2015]
• Index entries for sequences related to binary expansion of n
• Index entries for sequences related to polynomials in ring GF(2)[X]
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

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))].

Similar permutations for other bases: A263273 (base-3), A264994 (base-4), A264995 (base-5), A264979 (base-9).

Other related (binary) permutations: A056539, A193231.

Compositions of this permutation with other binary (or other base-related) permutations: A264965, A264966, A265329, A265369, A379471, A379472.

Compositions with permutations involving prime factorization: A245450, A245453, A266402, A266404, A293448, A366275, A366276.

Other derived permutations: A246200 [= a(3*n)/3], A266351, A302027, A302028, A345201, A356331, A356332, A356759, A366389.

See also A235027 (which is not a permutation).

Programs

Mathematica

Table[FromDigits[Reverse[IntegerDigits[n, 2]], 2]*2^IntegerExponent[n, 2], {n, 71}] (* Ivan Neretin, Jul 09 2015 *)

PARI

A030101(n) = if(n<1,0,subst(Polrev(binary(n)),x,2));
A057889(n) = if(!n,n,A030101(n/(2^valuation(n,2))) * (2^valuation(n, 2))); \\ Antti Karttunen, Dec 25 2024

Python

def a(n):
    x = bin(n)[2:]
    y = x[::-1]
    return int(str(int(y))+(len(x) - len(str(int(y))))*'0', 2)
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 11 2017

Python

def A057889(n): return int(bin(n>>(m:=(~n&n-1).bit_length()))[-1:1:-1],2)<Chai Wah Wu, Dec 25 2024

Formula

a(n) = A030101(A000265(n)) * A006519(n), with a(0)=0.

Extensions

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