login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A065359 Alternating bit sum for n: replace 2^k with (-1)^k in binary expansion of n. 30
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 (list; graph; refs; listen; history; text; internal format)
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

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

   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

Harry J. Smith, Table of n, a(n) for n = 0..1000

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

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

R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.

R. Stephan, Some divide-and-conquer sequences ...

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

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) SumAD(x)= { local(a=1, s=0); while (x>9, s+=a*(x-10*(x\10)); x\=10; a=-a); return(s + a*x) } baseE(x, b)= { local(d, e=0, f=1); while (x>0, d=x-b*(x\b); x\=b; e+=d*f; f*=10); return(e) } { for (n=0, 1000, b=baseE(n, 2); write("b065359.txt", n, " ", SumAD(b)) ) } \\ Harry J. Smith, Oct 17 2009

(PARI) for(n=0, 106, s=0; u=1; for(k=0, #binary(n)-1, s+=bittest(n, k)*u; u=-u); print1(s, ", ")) /* Washington Bomfim, Jan 18 2011 */

(Haskell)

a065359 0 = 0

a065359 n = - a065359 n' + m where (n', m) = divMod n 2

-- Reinhard Zumkeller, Mar 20 2015

CROSSREFS

Cf. A005536 (partial sums), A056832 (abs first differences), A010060 (mod 2).

Cf. A000120, A065360, A065368, A065081.

Cf. A004718.

Sequence in context: A319571 A086966 A140080 * A087372 A036431 A029407

Adjacent sequences:  A065356 A065357 A065358 * A065360 A065361 A065362

KEYWORD

base,easy,sign

AUTHOR

Marc LeBrun, Oct 31 2001

EXTENSIONS

More terms from Ralf Stephan, Jul 12 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 14 03:42 EDT 2020. Contains 335716 sequences. (Running on oeis4.)