cp's OEIS Frontend

A065620 a(0)=0; thereafter a(2n) = 2a(n), a(2n+1) = -2a(n) + 1.

%I A065620 #50 Jul 06 2025 18:27:32
%S A065620 0,1,2,-1,4,-3,-2,3,8,-7,-6,7,-4,5,6,-5,16,-15,-14,15,-12,13,14,-13,
%T A065620 -8,9,10,-9,12,-11,-10,11,32,-31,-30,31,-28,29,30,-29,-24,25,26,-25,
%U A065620 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
%N A065620 a(0)=0; thereafter a(2n) = 2a(n), a(2n+1) = -2a(n) + 1.
%C A065620 Reversing binary value of n: convert sum of powers of 2 in binary representation of n to alternating sum.
%C A065620 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).
%D A065620 Donald E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1969, Vol. 2, p. 178 (exercise 4.1. Nr. 27).
%H A065620 N. J. A. Sloane, <a href="/A065620/b065620.txt">Table of n, a(n) for n = 0..20000</a> (First 8192 terms from Reinhard Zumkeller)
%F A065620 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.
%F A065620 From _Antti Karttunen_, Aug 18 2014: (Start)
%F A065620 a(n) = A246160(n) - A246159(n).
%F A065620 a(A065621(n)) = n.
%F A065620 a(A048724(n)) = -n. (End)
%F A065620 a(n) = -A104895(n). - _M. F. Hasler_, Apr 16 2018
%F A065620 a(n) = (2*A265263(n) - n) * (2*A010060(n) - 1). - _Alan Michael Gómez Calderón_, Jul 01 2025
%e A065620 11 = 1 + 2 + 8 -> 1 - 2 + 8 = 7 = a(11).
%p A065620 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;
%p A065620 [seq(f(n),n=0..100)]; # _N. J. A. Sloane_, Apr 25 2018
%t A065620 a[0] = 0; a[n_]:= a[n]= If[OddQ[n], 1 - 2*a[(n-1)/2], 2*a[n/2]]; Array[a, 100, 0] (* _Amiram Eldar_, Sep 05 2023 *)
%o A065620 (Haskell)
%o A065620 import Data.List (transpose)
%o A065620 a065620 n = a065620_list !! n
%o A065620 a065620_list = 1 : concat (transpose [zs, map ((+ 1) . negate) zs])
%o A065620                where zs = map (* 2) a065620_list
%o A065620 -- _Reinhard Zumkeller_, Mar 26 2014
%o A065620 (Scheme)
%o A065620 (definec (A065620 n) (cond ((zero? n) n) ((even? n) (* 2 (A065620 (/ n 2)))) (else (+ 1 (* -2 (A065620 (/ (- n 1) 2)))))))
%o A065620 ;; using memoization-macro definec from IntSeq-library of _Antti Karttunen_, Aug 18 2014
%o A065620 (Python)
%o A065620 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
%o A065620 (Python)
%o A065620 def A065620(n):
%o A065620     c, a, b = 0, -1, 1
%o A065620     for j in bin(n)[-1:1:-1]:
%o A065620         if int(j):
%o A065620             c += (a:=-a)*b
%o A065620         b <<= 1
%o A065620     return c # _Chai Wah Wu_, Sep 19 2023
%o A065620 (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
%Y A065620 Cf. A010060, A048724, A065621, A246159, A246160, A265263.
%Y A065620 The negative of entry A104895.
%K A065620 base,easy,sign,look
%O A065620 0,3
%A A065620 _Marc LeBrun_, Nov 07 2001
%E A065620 Formula fixed by _Reinhard Zumkeller_, Mar 26 2014
%E A065620 Extended to a(0) = 0 by _M. F. Hasler_, Apr 16 2018
%E A065620 Edited by _N. J. A. Sloane_, Apr 25 2018