|
%I #41 Feb 14 2024 14:12:19
%S 1,2,7,4,13,14,11,8,25,26,31,28,21,22,19,16,49,50,55,52,61,62,59,56,
%T 41,42,47,44,37,38,35,32,97,98,103,100,109,110,107,104,121,122,127,
%U 124,117,118,115,112,81,82,87,84,93,94,91,88,73,74,79,76,69,70,67,64,193
%N Reversing binary representation of n. Converting sum of powers of 2 in binary representation of a(n) to alternating sum gives n.
%C a(0)=0. The alternation is applied only to the nonzero bits and does not depend on the exponent of two. All integers have a unique reversing binary representation (see cited exercise for proof). Complement of A048724.
%C A permutation of the "odious" numbers A000069.
%C Write n-1 and 2n-1 in binary and add them mod 2; example: n = 6, n-1 = 5 = 101 in binary, 2n-1 = 11 = 1011 in binary and their sum is 1110 = 14, so a(6) = 14. - _Philippe Deléham_, Apr 29 2005
%C As already pointed out, this is a permutation of the odious numbers A000069 and A010060(A000069(n)) = 1, so A010060(a(n)) = 1; and A010060(A048724(n)) = 0. - _Philippe Deléham_, Apr 29 2005. Also a(n) = A000069(A003188(n - 1)).
%D D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1969, Vol. 2, p. 178, (exercise 4.1. Nr. 27)
%H Reinhard Zumkeller, <a href="/A065621/b065621.txt">Table of n, a(n) for n = 1..8192</a>
%F a(n) = if n=0 or n=1 then n else b+2*a(b+(1-2*b)*n)/2) where b is the least significant bit in n.
%F a(n) = n XOR 2 (n - (n AND -n)).
%F a(1) = 1, a(2n) = 2*a(n), a(2n+1) = 2*a(n+1) - 2(-1)^n + 1. - _Ralf Stephan_, Aug 20 2003
%F a(n) = A048724(n-1) - (-1)^n. - _Ralf Stephan_, Sep 10 2003
%F a(n) = Sum_{k=0..n} (1-(-1)^round(-n/2^k))/2*2^k. - _Benoit Cloitre_, Apr 27 2005
%F Closely related to Gray codes in another way: a(n) = 2 * A003188(n-1) + (n mod 2); a(n) = 4 * A003188((n-1) div 2) + (n mod 4). - Matt Erbst (matt(AT)erbst.org), Jul 18 2006 [corrected by _Peter Munn_, Jan 30 2021]
%F a(n) = n XOR 2(n AND NOT -n). - _Chai Wah Wu_, Jun 29 2022
%F a(n) = A003188(2n-1). - _Friedjof Tellkamp_, Jan 18 2024
%e a(5) = 13 = 8 + 4 + 1 -> 8 - 4 + 1 = 5.
%t f[n_] := BitXor[n, 2 n + 1]; Array[f, 60, 0] (* _Robert G. Wilson v_, Jun 09 2010 *)
%o (PARI) a(n)=if(n<2,1,if(n%2==0,2*a(n/2),2*a((n+1)/2)-2*(-1)^((n-1)/2)+1))
%o (Haskell)
%o import Data.Bits (xor, (.&.))
%o a065621 n = n `xor` 2 * (n - n .&. negate n) :: Integer
%o -- _Reinhard Zumkeller_, Mar 26 2014
%o (Python)
%o def a(n): return n^(2*(n - (n & -n))) # _Indranil Ghosh_, Jun 04 2017
%o (Python)
%o def A065621(n): return n^ (n&~-n)<<1 # _Chai Wah Wu_, Jun 29 2022
%Y Cf. A003188, A065620, A048724, A072219, A073122.
%Y Differs from A115857 for the first time at n=19, where a(19)=55, while A115857(19)=23. Cf. A104895, A115872, A114389, A114390, A105081.
%Y Cf. A245471.
%K easy,nonn,look
%O 1,2
%A _Marc LeBrun_, Nov 07 2001
%E More terms from _Ralf Stephan_, Sep 08 2003
|
