login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A065620 a(0)=0; thereafter a(2n) = 2a(n), a(2n+1) = -2a(n) + 1. 19
0, 1, 2, -1, 4, -3, -2, 3, 8, -7, -6, 7, -4, 5, 6, -5, 16, -15, -14, 15, -12, 13, 14, -13, -8, 9, 10, -9, 12, -11, -10, 11, 32, -31, -30, 31, -28, 29, 30, -29, -24, 25, 26, -25, 28, -27, -26, 27, -16, 17, 18, -17, 20, -19, -18, 19, 24, -23, -22, 23, -20, 21, 22, -21, 64, -63, -62, 63, -60, 61, 62, -61, -56 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Reversing binary value of n: convert sum of powers of 2 in binary representation of n to alternating sum.

The alternation is applied only to the nonzero bits and does not depend on the exponent of 2. All integers have a unique reversing binary representation (see cited Knuth exercise for proof).

REFERENCES

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1969, Vol. 2, p. 178, (exercise 4.1. Nr. 27)

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..20000 (First 8192 terms from Reinhard Zumkeller)

FORMULA

a(n) = if n<2 then n else b+2*(1-2*b)*a((n-b)/2) where b is the least significant bit in n.

From Antti Karttunen, Aug 18 2014: (Start)

a(n) = A246160(n) - A246159(n).

a(A065621(n)) = n.

a(A048724(n)) = -n.

(End)

a(n) = -A104895(n). - M. F. Hasler, Apr 16 2018

EXAMPLE

11 = 1 + 2 + 8 -> 1 - 2 + 8 = 7 = a(11)

MAPLE

f:=proc(n) option remember; if n=0 then 0 elif (n mod 2) = 0 then 2*f(n/2) else 1-2*f((n-1)/2); fi; end;

[seq(f(n), n=0..100)]; # N. J. A. Sloane, Apr 25 2018

PROG

(Haskell)

import Data.List (transpose)

a065620 n = a065620_list !! n

a065620_list = 1 : concat (transpose [zs, map ((+ 1) . negate) zs])

               where zs = map (* 2) a065620_list

-- Reinhard Zumkeller, Mar 26 2014

(Scheme)

(definec (A065620 n) (cond ((zero? n) n) ((even? n) (* 2 (A065620 (/ n 2)))) (else (+ 1 (* -2 (A065620 (/ (- n 1) 2)))))))

;; using memoization-macro definec from IntSeq-library of Antti Karttunen, Aug 18 2014

(Python)

def a(n): return n if n<3 else 2*a(n/2) if n%2==0 else -2*a((n - 1)/2) + 1 # Indranil Ghosh, Jun 07 2017

(PARI) A065620(n, c=1)=sum(i=0, logint(n+!n, 2), if(bittest(n, i), (-1)^c++<<i)) \\ M. F. Hasler, Apr 16 2018

CROSSREFS

Cf. A065621, A048724, A246159, A246160.

The negative of entry A104895.

Sequence in context: A072650 A082497 A242364 * A104895 A103122 A214918

Adjacent sequences:  A065617 A065618 A065619 * A065621 A065622 A065623

KEYWORD

base,easy,sign,look

AUTHOR

Marc LeBrun, Nov 07 2001

EXTENSIONS

Formula fixed by Reinhard Zumkeller, Mar 26 2014

Extended to a(0) = 0 by M. F. Hasler, Apr 16 2018

Edited by N. J. A. Sloane, Apr 25 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 24 12:35 EDT 2021. Contains 347642 sequences. (Running on oeis4.)