|
Search: id:A065621
|
|
|
| A065621 |
|
Reversing binary representation of n. Converting sum of powers of 2 in binary representation of a(n) to alternating sum gives n. |
|
+0
11
|
|
| 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; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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 DELEHAM, Apr 29 2005
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 DELEHAM, Apr 29 2005. Also a(n) = A000069(A003188(n - 1)).
|
|
REFERENCES
|
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1969, Vol. 2, p. 178, (exercise 4.1. Nr. 27)
|
|
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) = 2a(n), a(2n+1) = 2a(n+1) - 2(-1)^n + 1. - Ralf Stephan (ralf(AT)ark.in-berlin.de), Aug 20 2003
a(n) = A048724(n-1) - (-1)^n. - Ralf Stephan (ralf(AT)ark.in-berlin.de), Sep 10 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) + (n mod 2) : a(n) := 4 * A003188(n div 2) + (n mod 2) . - Matt Erbst (matt(AT)erbst.org), Jul 18 2006
|
|
EXAMPLE
|
a(5) = 13 = 8 + 4 + 1 -> 8 - 4 + 1 = 5.
|
|
PROGRAM
|
(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))
|
|
CROSSREFS
|
Cf. A065620, A048724, A072219, A073122.
Differs from A115857 for the first time at n=19, where a(19)=55, while A115857(19)=23. Cf. A104895, A115872, A114389, A114390, A105081.
Sequence in context: A019779 A102514 A115857 this_sequence A036565 A054787 A013623
Adjacent sequences: A065618 A065619 A065620 this_sequence A065622 A065623 A065624
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Marc LeBrun (mlb(AT)well.com), Nov 07 2001
|
|
EXTENSIONS
|
More terms from Ralf Stephan (ralf(AT)ark.in-berlin.de), Sep 08 2003
|
|
|
Search completed in 0.006 seconds
|
