A053985 - OEIS

%I #56 Nov 19 2022 06:20:42

%S 0,1,-2,-1,4,5,2,3,-8,-7,-10,-9,-4,-3,-6,-5,16,17,14,15,20,21,18,19,8,

%T 9,6,7,12,13,10,11,-32,-31,-34,-33,-28,-27,-30,-29,-40,-39,-42,-41,

%U -36,-35,-38,-37,-16,-15,-18,-17,-12,-11,-14,-13,-24,-23,-26,-25,-20,-19

%N Replace 2^k with (-2)^k in binary expansion of n.

%C Base 2 representation for n (in lexicographic order) converted from base -2 to base 10.

%C Maps natural numbers uniquely onto integers; within each group of positive values, maximum is in A002450; a(n)=n iff n can be written only with 1's and 0's in base 4 (A000695).

%C a(n) = A004514(n) - n. - _Reinhard Zumkeller_, Dec 27 2003

%C Schroeppel gives formula n = (a(n) + b) XOR b where b = binary ...101010, and notes this formula is reversible.  The reverse a(n) = (n XOR b) - b is a bit twiddle to transform 1 bits to -1.  Odd position 0 or 1 in n is flipped by "XOR b" to 1 or 0, then "- b" gives 0 or -1.  Only odd position 1's are changed, so b can be any length sure to cover those. - _Kevin Ryde_, Jun 26 2020

%H Rémy Sigrist, <a href="/A053985/b053985.txt">Table of n, a(n) for n = 0..8191</a>

%H Michael Beeler, R. William Gosper, and Richard Schroeppel, <a href="https://dspace.mit.edu/handle/1721.1/6086">HAKMEM</a>, MIT Artificial Intelligence Laboratory report AIM-239, February 1972, item 128 by Schroeppel, page 62.  Also <a href="http://www.inwap.com/pdp10/hbaker/hakmem/Figure7.html">HTML transcription</a>.  Figure 7 path drawn 0, 1, -2, -1, 4, ... is the present sequence.

%H Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, pp. 45, 49.

%H Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, <a href="https://arxiv.org/abs/2012.04625">Finding structure in sequences of real numbers via graph theory: a problem list</a>, arXiv:2012.04625 [math.CO], 2020-2021.

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%F From _Ralf Stephan_, Jun 13 2003: (Start)

%F G.f.: (1/(1-x)) * Sum_{k>=0} (-2)^k*x^2^k/(1+x^2^k).

%F a(0) = 0, a(2*n) = -2*a(n), a(2*n+1) = -2*a(n)+1. (End)

%F a(n) = Sum_{k>=0} A030308(n,k)*A122803(k). - _Philippe Deléham_, Oct 15 2011

%F a(n) = (n XOR b) - b where b = binary ..101010 [Schroeppel].  Any b of this form (A020988) with bitlength(b) >= bitlength(n) suits. - _Kevin Ryde_, Jun 26 2020

%e a(9)=-7 because 9 is written 1001 base 2 and (-2)^3 + (-2)^0 = -8 + 1 = -7.

%e Or by Schroeppel's formula, b = binary 1010 then a(9) = (1001 XOR 1010) - 1010 = decimal -7. - _Kevin Ryde_, Jun 26 2020

%t f[n_Integer, b_Integer] := Block[{l = IntegerDigits[n]}, Sum[l[[ -i]]*(-b)^(i - 1), {i, 1, Length[l]}]]; a = Table[ FromDigits[ IntegerDigits[n, 2]], {n, 0, 80}]; b = {}; Do[b = Append[b, f[a[[n]], 2]], {n, 1, 80}]; b

%t (* Second program: *)

%t Array[FromDigits[IntegerDigits[#, 2], -2] &, 62, 0] (* _Michael De Vlieger_, Jun 27 2020 *)

%o (PARI) a(n) = fromdigits(binary(n), -2) \\ _Rémy Sigrist_, Sep 01 2018

%o (Python)

%o def A053985(n): return  -(b:=int('10'*(n.bit_length()+1>>1),2)) + (n^b) if n else 0 # _Chai Wah Wu_, Nov 18 2022

%Y Inverse of A005351. Cf. A039724, A007088, A065369, A073791, A073792, A073793, A073794, A073795, A073796 and A073835.

%K base,easy,sign

%O 0,3

%A _Henry Bottomley_, Apr 03 2000