A068639 a(0) = 0, a(n) = a(n-1) + (-1)^p(n) for n >= 1, where p(n) = highest power of 2 dividing n.

0, 1, 0, 1, 2, 3, 2, 3, 2, 3, 2, 3, 4, 5, 4, 5, 6, 7, 6, 7, 8, 9, 8, 9, 8, 9, 8, 9, 10, 11, 10, 11, 10, 11, 10, 11, 12, 13, 12, 13, 12, 13, 12, 13, 14, 15, 14, 15, 16, 17, 16, 17, 18, 19, 18, 19, 18, 19, 18, 19, 20, 21, 20, 21, 22, 23, 22, 23, 24, 25, 24, 25, 24, 25, 24, 25, 26, 27, 26

Offset: 0

Author

N. J. A. Sloane, Oct 01 2003

Keywords

• nonn
• easy

Links

• Paolo Xausa, Table of n, a(n) for n = 0..10000
• J.-P. Allouche and Jeffrey Shallit, The Ring of k-regular Sequences, II
• J.-P. Allouche and Jeffrey Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
• Ralf Stephan, Some divide-and-conquer sequences ...
• Ralf Stephan, Table of generating functions

Crossrefs

Cf. A050292, A065359, A087733.

Programs

Mathematica

A068639[n_] := (n + 2*Total[(-1)^Range[0, Max[0, BitLength[n] - 1]]*Reverse[IntegerDigits[n, 2]]])/3;
Array[A068639, 101, 0] (* or *)
Join[{0}, Accumulate[(-1)^IntegerExponent[Range[100], 2]]] (* Paolo Xausa, Jun 05 2025 *)

PARI

a(n)=if(n<1,0,ceil(n/2)-a(n-ceil(n/2)))

Formula

a(n) = (n+2*A065359(n))/3; a(n) is asymptotic to n/3. - Benoit Cloitre, Oct 04 2003

From Ralf Stephan, Oct 17 2003: (Start)

a(0)=0, a(2n) = -a(n) + n, a(2n+1) = -a(n) + n + 1.

a(n) = (1/2) * (A050292(n) + A065359(n)).

G.f.: (1/2) * 1/(1-x) * Sum_{k>=0} (-1)^k*t/(1-t^2) where t=x^2^k. (End)

a(0)=0 then a(n) = ceiling(n/2)-a(n-ceiling(n/2)). - Benoit Cloitre, May 03 2004

Extensions

More terms from John W. Layman and Robert G. Wilson v, Oct 02 2003