cp's OEIS Frontend

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.

%I A056539 #38 Jul 02 2025 23:16:18
%S A056539 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,
%T A056539 20,27,24,23,16,31,62,33,46,49,54,41,38,57,58,37,42,53,50,45,34,61,60,
%U A056539 35,44,51,52,43,36,59,56,39,40,55,48,47,32,63,126,65,94,97,110,81,78
%N 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.
%H A056539 Paul Tek, <a href="/A056539/b056539.txt">Table of n, a(n) for n = 0..8191</a>
%H A056539 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A056539 a(2n) = A036044(2n), a(2n+1) = A030101(2n+1). - _Antti Karttunen_, Feb 14 2003
%e A056539 n:                     0, 1,  2,  3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15
%e A056539 binary expansion:      0, 1, 10, 11, 100, 101, 110, 111,1000,1001,1010,1011,1100,1101,1110,1111
%e A056539 reversed/complemented: 0, 1, 10, 11, 110, 101, 100, 111,1110,1001,1010,1101,1100,1011,1000,1111
%p A056539 [seq(runcounts2binexp(reverse(binexp2runcounts(j))),j=0..511)];
%p A056539 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;
%p A056539 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;
%p A056539 # reverse given in A056538
%t A056539 A056539[n_] := If[n == 0, 0, FromDigits[Reverse[If[Last[#] == 1, #, 1-#]], 2] & [IntegerDigits[n, 2]]];
%t A056539 Array[A056539, 100, 0] (* _Paolo Xausa_, Nov 28 2024 *)
%o A056539 (Python)
%o A056539 def a005811(n): return bin(n^(n>>1))[2:].count("1")
%o A056539 def a(n):
%o A056539     if n==0: return 0
%o A056539     x=bin(n)[2:][::-1]
%o A056539     if a005811(n)%2==1: return int(x, 2)
%o A056539     z=''.join('1' if i == '0' else '0' for i in x)
%o A056539     return int(z, 2) # _Indranil Ghosh_, Apr 29 2017
%Y A056539 Cf. A054429.
%Y A056539 When restricted to A014486 induces another permutation, A057164. A105726 is a "deep" variant.
%K A056539 base,nonn,look
%O A056539 0,3
%A A056539 _Antti Karttunen_, Jun 20 2000