|
|
A065621
|
|
Reversing binary representation of n. Converting sum of powers of 2 in binary representation of a(n) to alternating sum gives n.
|
|
58
|
|
|
1, 2, 7, 4, 13, 14, 11, 8, 25, 26, 31, 28, 21, 22, 19, 16, 49, 50, 55, 52, 61, 62, 59, 56, 41, 42, 47, 44, 37, 38, 35, 32, 97, 98, 103, 100, 109, 110, 107, 104, 121, 122, 127, 124, 117, 118, 115, 112, 81, 82, 87, 84, 93, 94, 91, 88, 73, 74, 79, 76, 69, 70, 67, 64, 193
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
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.
A permutation of the "odious" numbers A000069.
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
|
|
REFERENCES
|
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1969, Vol. 2, p. 178, (exercise 4.1. Nr. 27)
|
|
LINKS
|
|
|
FORMULA
|
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.
a(n) = n XOR 2 (n - (n AND -n)).
a(1) = 1, a(2n) = 2*a(n), a(2n+1) = 2*a(n+1) - 2(-1)^n + 1. - Ralf Stephan, Aug 20 2003
a(n) = Sum_{k=0..n} (1-(-1)^round(-n/2^k))/2*2^k. - Benoit Cloitre, Apr 27 2005
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]
a(n) = n XOR 2(n AND NOT -n). - Chai Wah Wu, Jun 29 2022
|
|
EXAMPLE
|
a(5) = 13 = 8 + 4 + 1 -> 8 - 4 + 1 = 5.
|
|
MATHEMATICA
|
|
|
PROG
|
(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))
(Haskell)
import Data.Bits (xor, (.&.))
a065621 n = n `xor` 2 * (n - n .&. negate n) :: Integer
(Python)
(Python)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|