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

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

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

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

Example

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

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]

Prog

(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
(Haskell)
a065359 0 = 0
a065359 n = - a065359 n' + m where (n', m) = divMod n 2
-- Reinhard Zumkeller, Mar 20 2015
(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

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

Sequence in context: A086966 A140080 A345927 * A087372 A036431 A029407

Adjacent sequences: A065356 A065357 A065358 * A065360 A065361 A065362

Keyword

base,easy,sign,changed

Author

Marc LeBrun, Oct 31 2001

Extensions

More terms from Ralf Stephan, Jul 12 2003

Status

approved