A083905 -id:A083905 - cp's OEIS frontend

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

Marc LeBrun, Oct 31 2001

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

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

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

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

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

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

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

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

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

a(n) = if(n==0, 0, 2*hammingweight(bitand(n, ((4<<(2*logint(n,4)))-1)/3)) - hammingweight(n)) \\ Andrew Howroyd, Dec 14 2024

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

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

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

More terms from Ralf Stephan, Jul 12 2003

A030300 Runs have lengths 2^n, n >= 0.

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Jean-Paul Delahaye

An example of a sequence with property that the fraction of 1's in the first n terms does not converge to a limit. - N. J. A. Sloane, Sep 24 2007
Image, under the coding sending a,d,e -> 1 and b,c -> 0, of the fixed point, starting with a, of the morphism a -> ab, b -> cd, c -> ee, d -> eb, e -> cc. - Jeffrey Shallit, May 14 2016
This sequence taken as digits of a base-b fraction is g(1/b) = Sum_{n>=1} a(n)/b^n = b/(b-1) * Sum_{k>=0} (-1)^k/b^(2^k) per the generating function below.  With initial 0, it is binary expansion .01001111 = A275975.  With initial 0 and digits 2*a(n), it is ternary expansion .02002222 = A160386.  These and in general g(1/b) for any integer b>=2 are among forms which Kempner showed are transcendental. - Kevin Ryde, Sep 07 2019

Antti Karttunen, Table of n, a(n) for n = 1..65537
Aubrey J. Kempner, On Transcendental Numbers, Transactions of the American Mathematical Society, volume 17, number 4, October 1916, pages 476-482.
Kevin Ryde, Plot of A079947(n)/n, illustrating proportion of 1s in the first n terms here does not converge (but oscillates with rises and falls by hyperbolas)
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Index entries for sequences related to binary expansion of n
Index entries for characteristic functions

Cf. A030301. Partial sums give A079947.
Cf. A065359, A083905.
Characteristic function of A053738.

f0 := n->[seq(0,i=1..2^n)]; f1 := n->[seq(1,i=1..2^n)]; s := []; for i from 0 to 4 do s := [op(s), op(f1(2*i)), op(f0(2*i+1))]; od: A030300 := s;

nMax = 6; Table[1 - Mod[n, 2], {n, 0, nMax}, {2^n}] // Flatten (* Jean-François Alcover, Oct 20 2016 *)

a(n) = if(n, !(logint(n,2)%2)); /* Kevin Ryde, Aug 02 2019 */

def A030300(n): return n.bit_length()&1 # Chai Wah Wu, Jan 30 2023

a(n) = A065359(n) + A083905(n).
a(n) = (1/2)*(1+(-1)^floor(log_2(n))). - Benoit Cloitre, Feb 22 2003
G.f.: 1/(1-x) * Sum_{k>=0} (-1)^k*x^2^k. - Ralf Stephan, Jul 12 2003
a(n) = 1 - a(floor(n/2)). - Vladeta Jovovic, Aug 04 2003
a(n) = A115253(2n, n) mod 2. - Paul Barry, Jan 18 2006
a(n) = 1 - A030301(n). - Antti Karttunen, Oct 10 2017

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Formula

Extensions

A030300 Runs have lengths 2^n, n >= 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula