A056539 Self-inverse permutation: reverse the bits in binary expansion of n and also complement them (0->1, 1->0) if the run count (A005811) is even.

0, 1, 2, 3, 6, 5, 4, 7, 14, 9, 10, 13, 12, 11, 8, 15, 30, 17, 22, 25, 26, 21, 18, 29, 28, 19, 20, 27, 24, 23, 16, 31, 62, 33, 46, 49, 54, 41, 38, 57, 58, 37, 42, 53, 50, 45, 34, 61, 60, 35, 44, 51, 52, 43, 36, 59, 56, 39, 40, 55, 48, 47, 32, 63, 126, 65, 94, 97, 110, 81, 78

Offset: 0

Author

Antti Karttunen, Jun 20 2000

Keywords

• base
• nonn
• look

Examples

			n:                     0, 1,  2,  3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15
binary expansion:      0, 1, 10, 11, 100, 101, 110, 111,1000,1001,1010,1011,1100,1101,1110,1111
reversed/complemented: 0, 1, 10, 11, 110, 101, 100, 111,1110,1001,1010,1101,1100,1011,1000,1111
		

Links

• Paul Tek, Table of n, a(n) for n = 0..8191
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A054429.

When restricted to A014486 induces another permutation, A057164. A105726 is a "deep" variant.

Programs

Maple

[seq(runcounts2binexp(reverse(binexp2runcounts(j))),j=0..511)];
runcounts2binexp := proc(c) local i,e,n; n := 0; for i from 1 to nops(c) do e := c[i]; n := ((2^e)*n) + ((i mod 2)*((2^e)-1)); od; RETURN(n); end;
binexp2runcounts := proc(nn) local n,a,p,c; n := nn; a := []; p := (`mod`(n,2)); c := 0; while(n > 0) do c := c+1; n := floor(n/2); if((`mod`(n,2)) <> p) then a := [c,op(a)]; c := 0; p := (`mod`(p+1,2)); fi; od; RETURN(a); end;
# reverse given in A056538

Mathematica

A056539[n_] := If[n == 0, 0, FromDigits[Reverse[If[Last[#] == 1, #, 1-#]], 2] & [IntegerDigits[n, 2]]];
Array[A056539, 100, 0] (* Paolo Xausa, Nov 28 2024 *)

Python

def a005811(n): return bin(n^(n>>1))[2:].count("1")
def a(n):
    if n==0: return 0
    x=bin(n)[2:][::-1]
    if a005811(n)%2==1: return int(x, 2)
    z=''.join('1' if i == '0' else '0' for i in x)
    return int(z, 2) # Indranil Ghosh, Apr 29 2017

Formula

a(2n) = A036044(2n), a(2n+1) = A030101(2n+1). - Antti Karttunen, Feb 14 2003