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

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, 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, -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

Offset: 0

Author

Marc LeBrun, Oct 31 2001

Keywords

• base
• easy
• sign

Comments

Notation: (2)[n](-1)

From David W. Wilson and Ralf Stephan, Jan 09 2007: (Start)

a(n) is even iff n in A001969; a(n) is odd iff n in A000069.

a(n) == 0 (mod 3) iff n == 0 (mod 3).

a(n) == 0 (mod 6) iff (n == 0 (mod 3) and n/3 not in A036556).

a(n) == 3 (mod 6) iff (n == 0 (mod 3) and n/3 in A036556). (End)

a(n) = A030300(n) - A083905(n). - Ralf Stephan, Jul 12 2003

From Robert G. Wilson v, Feb 15 2011: (Start)

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.;

a(n)=-3 only if n mod 3 = 0,

a(n)=-2 only if n mod 3 = 1,

a(n)=-1 only if n mod 3 = 2,

a(n)= 0 only if n mod 3 = 0,

a(n)= 1 only if n mod 3 = 1,

a(n)= 2 only if n mod 3 = 2,

a(n)= 3 only if n mod 3 = 0, ..., . (End)

a(n) modulo 2 is the Prouhet-Thue-Morse sequence A010060. - Philippe Deléham, Oct 20 2011

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

Examples

			Alternating bit sum for 11 = 1011 in binary is 1 - 1 + 0 - 1 = -1, so a(11) = -1.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..65535 (terms 0..1000 from Harry J. Smith)
• J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197. [Preprint.]
• J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
• H.-K. Hwang, S. Janson and T.-H. Tsai. Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications. Preprint, 2016.
• H.-K. Hwang, S. Janson and T.-H. Tsai. Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications. ACM Transactions on Algorithms, 13:4 (2017), #47. DOI:10.1145/3127585.
• Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 45.
• Helge von Koch, Une Méthode Géométrique Élémentaire pour l'Étude de Certaines Questions de la Théorie des Courbes Planes, Acta Arithmetica, volume 30, 1906, pages 145-174.
• William Paulsen, wpaulsen(AT)csm.astate.edu, Partitioning the [prime] maze
• Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
• Ralf Stephan, Some divide-and-conquer sequences ...
• Ralf Stephan, Table of generating functions

Crossrefs

Cf. A005536 (partial sums), A056832 (abs first differences), A010060 (mod 2), A039004 (indices of 0's).

Cf. A000120, A065360, A065081, A019565, A195017.

Cf. also A004718.

Cf. analogous sequences for bases 3-10: A065368, A346688, A346689, A346690, A346691, A346731, A346732, A055017 and also A373605 (for primorial base).

Programs

Haskell

a065359 0 = 0
a065359 n = - a065359 n' + m where (n', m) = divMod n 2
-- Reinhard Zumkeller, Mar 20 2015

Maple

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

Mathematica

f[0]=0; f[n_] := Plus @@ (-(-1)^Range[ Floor[ Log2@ n + 1]] Reverse@ IntegerDigits[n, 2]); Array[ f, 107, 0]

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 */

PARI

a(n) = my(b=binary(n)); b*[(-1)^k|k<-[-#b+1..0]]~; \\ Ruud H.G. van Tol, Oct 16 2023

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

Python

def a(n):
    return sum((-1)**k for k, bi in enumerate(bin(n)[2:][::-1]) if bi=='1')
print([a(n) for n in range(107)]) # Michael S. Branicky, Jul 13 2021

Python

from sympy.ntheory import digits
def A065359(n): return sum((0,1,-1,0)[i] for i in digits(n,4)[1:]) # Chai Wah Wu, Jul 19 2024

Formula

G.f.: (1/(1-x)) * Sum_{k>=0} (-1)^k*x^2^k/(1+x^2^k). - Ralf Stephan, Mar 07 2003

a(0) = 0, a(2n) = -a(n), a(2n+1) = 1-a(n). - Ralf Stephan, Mar 07 2003

a(n) = Sum_{k>=0} A030308(n,k)*(-1)^k. - Philippe Deléham, Oct 20 2011

a(n) = -a(floor(n/2)) + n mod 2. - Reinhard Zumkeller, Mar 20 2015

a(n) = A139351(n) - A139352(n). - Kevin Ryde, Jan 24 2020

G.f. A(x) satisfies: A(x) = x / (1 - x^2) - (1 + x) * A(x^2). - Ilya Gutkovskiy, Jul 28 2021

a(n) = A195017(A019565(n)). - Antti Karttunen, Jun 19 2024

Extensions

More terms from Ralf Stephan, Jul 12 2003