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,3

Links

Paul Tek, Table of n, a(n) for n = 0..8191

Index entries for sequences that are permutations of the natural numbers

Formula

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

Example

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

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

Prog

(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

Crossrefs

Cf. A054429.

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

Sequence in context: A284459 A106451 A357523 * A105726 A336962 A342102

Adjacent sequences: A056536 A056537 A056538 * A056540 A056541 A056542

Keyword

base,nonn,look

Author

Antti Karttunen, Jun 20, 2000

Status

approved