cp's OEIS Frontend

A065359 Alternating bit sum for n: replace 2^k with (-1)^k in binary expansion of n.

%I A065359 #105 Dec 14 2024 18:26:08
%S A065359 0,1,-1,0,1,2,0,1,-1,0,-2,-1,0,1,-1,0,1,2,0,1,2,3,1,2,0,1,-1,0,1,2,0,
%T A065359 1,-1,0,-2,-1,0,1,-1,0,-2,-1,-3,-2,-1,0,-2,-1,0,1,-1,0,1,2,0,1,-1,0,
%U A065359 -2,-1,0,1,-1,0,1,2,0,1,2,3,1,2,0,1,-1,0,1,2,0,1,2,3,1,2,3,4,2,3,1,2,0,1,2,3,1,2,0,1,-1,0,1,2,0,1,-1,0,-2
%N A065359 Alternating bit sum for n: replace 2^k with (-1)^k in binary expansion of n.
%C A065359 Notation: (2)[n](-1)
%C A065359 From _David W. Wilson_ and _Ralf Stephan_, Jan 09 2007: (Start)
%C A065359 a(n) is even iff n in A001969; a(n) is odd iff n in A000069.
%C A065359 a(n) == 0 (mod 3) iff n == 0 (mod 3).
%C A065359 a(n) == 0 (mod 6) iff (n == 0 (mod 3) and n/3 not in A036556).
%C A065359 a(n) == 3 (mod 6) iff (n == 0 (mod 3) and n/3 in A036556). (End)
%C A065359 a(n) = A030300(n) - A083905(n). - _Ralf Stephan_, Jul 12 2003
%C A065359 From _Robert G. Wilson v_, Feb 15 2011: (Start)
%C A065359 First occurrence of k and -k: 0, 1, 2, 5, 10, 21, 42, 85, ..., (A000975); i.e., first 0 occurs for 0, first 1 occurs for 1, first -1 occurs at 2, first 2 occurs for 5, etc.;
%C A065359   a(n)=-3 only if n mod 3 = 0,
%C A065359   a(n)=-2 only if n mod 3 = 1,
%C A065359   a(n)=-1 only if n mod 3 = 2,
%C A065359   a(n)= 0 only if n mod 3 = 0,
%C A065359   a(n)= 1 only if n mod 3 = 1,
%C A065359   a(n)= 2 only if n mod 3 = 2,
%C A065359   a(n)= 3 only if n mod 3 = 0, ..., . (End)
%C A065359 a(n) modulo 2 is the Prouhet-Thue-Morse sequence A010060. - _Philippe Deléham_, Oct 20 2011
%C A065359 In the Koch curve, number the segments starting with n=0 for the first segment. The net direction (i.e., the sum of the preceding turns) of segment n is a(n)*60 degrees. This is since in the curve each base-4 digit 0,1,2,3 of n is a sub-curve directed respectively 0, +60, -60, 0 degrees, which is the net 0,+1,-1,0 of two bits in the sum here. - _Kevin Ryde_, Jan 24 2020
%H A065359 Antti Karttunen, <a href="/A065359/b065359.txt">Table of n, a(n) for n = 0..65535</a> (terms 0..1000 from Harry J. Smith)
%H A065359 J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197. [<a href="http://www.math.jussieu.fr/~allouche/kreg2.ps">Preprint</a>.]
%H A065359 J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/S0304-3975(03)00090-2">The ring of k-regular sequences, II</a>, Theoret. Computer Sci., 307 (2003), 3-29.
%H A065359 H.-K. Hwang, S. Janson and T.-H. Tsai. <a href="http://algo.stat.sinica.edu.tw/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>. Preprint, 2016.
%H A065359 H.-K. Hwang, S. Janson and T.-H. Tsai. <a href="http://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>. ACM Transactions on Algorithms, 13:4 (2017), #47. DOI:10.1145/3127585.
%H A065359 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, p. 45.
%H A065359 Helge von Koch, <a href="http://archive.org/details/actamathematica11lefgoog">Une Méthode Géométrique Élémentaire pour l'Étude de Certaines Questions de la Théorie des Courbes Planes</a>, Acta Arithmetica, volume 30, 1906, pages 145-174.
%H A065359 William Paulsen, wpaulsen(AT)csm.astate.edu, <a href="http://myweb.astate.edu/wpaulsen/primemaze/mazepart.html">Partitioning the [prime] maze</a>
%H A065359 Ralf Stephan, <a href="https://arxiv.org/abs/math/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.
%H A065359 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H A065359 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%F A065359 G.f.: (1/(1-x)) * Sum_{k>=0} (-1)^k*x^2^k/(1+x^2^k). - _Ralf Stephan_, Mar 07 2003
%F A065359 a(0) = 0, a(2n) = -a(n), a(2n+1) = 1-a(n). - _Ralf Stephan_, Mar 07 2003
%F A065359 a(n) = Sum_{k>=0} A030308(n,k)*(-1)^k. - _Philippe Deléham_, Oct 20 2011
%F A065359 a(n) = -a(floor(n/2)) + n mod 2. - _Reinhard Zumkeller_, Mar 20 2015
%F A065359 a(n) = A139351(n) - A139352(n). - _Kevin Ryde_, Jan 24 2020
%F A065359 G.f. A(x) satisfies: A(x) = x / (1 - x^2) - (1 + x) * A(x^2). - _Ilya Gutkovskiy_, Jul 28 2021
%F A065359 a(n) = A195017(A019565(n)). - _Antti Karttunen_, Jun 19 2024
%e A065359 Alternating bit sum for 11 = 1011 in binary is 1 - 1 + 0 - 1 = -1, so a(11) = -1.
%p A065359 A065359 := proc(n) local dgs ; dgs := convert(n,base,2) ; add( -op(i,dgs)*(-1)^i,i=1..nops(dgs)) ; end proc: # _R. J. Mathar_, Feb 04 2011
%t A065359 f[0]=0; f[n_] := Plus @@ (-(-1)^Range[ Floor[ Log2@ n + 1]] Reverse@ IntegerDigits[n, 2]); Array[ f, 107, 0]
%o A065359 (PARI) a(n) = my(s=0, u=1); for(k=0,#binary(n)-1,s+=bittest(n,k)*u;u=-u);s /* _Washington Bomfim_, Jan 18 2011 */
%o A065359 (PARI) a(n) = my(b=binary(n)); b*[(-1)^k|k<-[-#b+1..0]]~; \\ _Ruud H.G. van Tol_, Oct 16 2023
%o A065359 (PARI) a(n) = if(n==0, 0, 2*hammingweight(bitand(n, ((4<<(2*logint(n,4)))-1)/3)) - hammingweight(n)) \\ _Andrew Howroyd_, Dec 14 2024
%o A065359 (Haskell)
%o A065359 a065359 0 = 0
%o A065359 a065359 n = - a065359 n' + m where (n', m) = divMod n 2
%o A065359 -- _Reinhard Zumkeller_, Mar 20 2015
%o A065359 (Python)
%o A065359 def a(n):
%o A065359     return sum((-1)**k for k, bi in enumerate(bin(n)[2:][::-1]) if bi=='1')
%o A065359 print([a(n) for n in range(107)]) # _Michael S. Branicky_, Jul 13 2021
%o A065359 (Python)
%o A065359 from sympy.ntheory import digits
%o A065359 def A065359(n): return sum((0,1,-1,0)[i] for i in digits(n,4)[1:]) # _Chai Wah Wu_, Jul 19 2024
%Y A065359 Cf. A005536 (partial sums), A056832 (abs first differences), A010060 (mod 2), A039004 (indices of 0's).
%Y A065359 Cf. A000120, A065360, A065081, A019565, A195017.
%Y A065359 Cf. also A004718.
%Y A065359 Cf. analogous sequences for bases 3-10: A065368, A346688, A346689, A346690, A346691, A346731, A346732, A055017 and also A373605 (for primorial base).
%K A065359 base,easy,sign
%O A065359 0,6
%A A065359 _Marc LeBrun_, Oct 31 2001
%E A065359 More terms from _Ralf Stephan_, Jul 12 2003