|
%I #18 Mar 23 2018 06:09:41
%S 2,1,3,4,6,5,7,8,10,9,11,12,14,13,15,32,34,33,35,36,38,37,39,40,42,41,
%T 43,44,46,45,47,16,18,17,19,20,22,21,23,24,26,25,27,28,30,29,31,48,50,
%U 49,51,52,54,53,55,56,58,57,59,60,62,61,63,64,66,65,67
%N a(1) = 2, a(2) = 1, and for any n > 2 with binary expansion Sum_{i=0..k} b_i * 2^i, a(n) = Sum_{i=0..k} b_i * 2^(a(i+1)-1).
%C More informally, in binary, the a(k)-th bit of a(n) is set iff the k-th bit of n is set (where the least significant bit has index 1).
%C For any k >= 0, the restriction of this sequence to the first A007013(k) terms is a self-inverse permutation preserving the Hamming weight; this property can be proven by induction.
%C This sequence is a self-inverse permutation of the natural numbers.
%C This sequence has infinitely many fixed points (A300950); for any k >= 0, at least one of 2^k or 2^k + a(2^k) is a fixed point.
%C See also A300955 and A300956 for sequences in the same vein.
%H Rémy Sigrist, <a href="/A300948/b300948.txt">Table of n, a(n) for n = 1..10000</a>
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A000120(a(n)) = A000120(n).
%F a(a(n)) = n.
%e a(3) = a(2^1 + 2^0) = 2^(a(2)-1) + 2^(a(1)-1) = 2^0 + 2^1 = 3.
%e a(4) = a(2^2) = 2^(a(3)-1) = 2^2 = 4.
%e a(6) = a(2^2 + 2^1) = 2^(a(3)-1) + 2^(a(2)-1) = 2^2 + 2^0 = 5.
%e a(42) = a(2^5 + 2^3 + 2^1) = 2^(a(6)-1) + 2^(a(4)-1) + 2^(a(2)-1) = 2^4 + 2^3 + 2^0 = 25.
%t a[1] = 2; a[2] = 1; a[n_] := a[n] = With[{b = IntegerDigits[n, 2] // Reverse}, Sum[If[b[[i]] == 1, 2^(a[i]-1), 0], {i, Length[b]}]]; Array[a, 100] (* _Jean-François Alcover_, Mar 17 2018 *)
%o (PARI) a(n) = if (n==1, 2, n==2, 1, my (b=Vecrev(binary(n))); sum(i=1, #b, if (b[i], 2^(a(i)-1), 0)))
%Y Cf. A000120, A007013, A300950 (fixed points), A300955, A300956.
%K nonn,base
%O 1,1
%A _Rémy Sigrist_, Mar 16 2018
|
