|
%I #29 Jan 25 2022 09:56:14
%S 0,1,3,2,4,5,7,6,12,13,15,14,8,9,11,10,16,17,19,18,20,21,23,22,28,29,
%T 31,30,24,25,27,26,48,49,51,50,52,53,55,54,60,61,63,62,56,57,59,58,32,
%U 33,35,34,36,37,39,38,44,45,47,46,40,41,43,42,64,65,67,66,68,69,71,70
%N Simple self-inverse permutation: Write n in base 4, then replace each digit '2' with '3' and vice versa, then convert back to decimal.
%H A. Karttunen, <a href="/A163241/b163241.txt">Table of n, a(n) for n = 0..1023</a>
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F a(n) = A000695(A003987bi(A059905(n),A059906(n))) + 2*A000695(A059906(n)), where A003987bi is binary XOR.
%e 43 in quaternary base (A007090) is written as '223' (2*16 + 2*4 + 3), which is then mapped to '332' = 3*16 + 3*4 + 2 = 62, thus a(43) = 62, and likewise a(62) = 43.
%p a:= proc(n) option remember; `if`(n=0, 0,
%p a(iquo(n, 4, 'r'))*4+[0, 1, 3, 2][r+1])
%p end:
%p seq(a(n), n=0..71); # _Alois P. Heinz_, Jan 25 2022
%t Table[FromDigits[IntegerDigits[n,4]/.{2->a,3->b}/.{a->3,b->2},4],{n,0,75}] (* _Harvey P. Dale_, Nov 29 2011 *)
%o (Scheme) (define (A163241 n) (+ (A000695 (A003987bi (A059905 n) (A059906 n))) (* 2 (A000695 (A059906 n)))))
%o (Python)
%o def a000695(n):
%o n=bin(n)[2:]
%o x=len(n)
%o return sum([int(n[i])*4**(x - 1 - i) for i in range(x)])
%o def a059905(n): return sum([(n>>2*i&1)<<i for i in range(len(bin(n)[2:])//2 + 1)])
%o def a059906(n):
%o x=[int(k) for k in list(bin(n)[2:])][::-1]
%o return sum([x[2*i + 1]*2**i for i in range(len(x)//2)])
%o def a(n): return a000695(a059905(n)^a059906(n)) + 2*a000695(a059906(n))
%o print([a(n) for n in range(101)]) # _Indranil Ghosh_, Jun 26 2017
%o (PARI) f(d) = if (d==2, 4, if (x==d, 2, d));
%o a(n) = fromdigits(apply(f, digits(n, 4)), 4); \\ _Michel Marcus_, Jun 28 2017
%o (C) uint32_t a(uint32_t n) { return n ^ ((n >> 1) & 0x55555555); } // _Falk Hüffner_, Jan 22 2022
%Y Cf. A048647, A007090, A003987.
%K nonn,base,easy
%O 0,3
%A _Antti Karttunen_, Jul 29 2009
%E Edited by _Charles R Greathouse IV_, Nov 01 2009
|
