cp's OEIS Frontend

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

%I A068639 #45 Jun 09 2025 10:36:41
%S A068639 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,
%T A068639 10,11,10,11,12,13,12,13,12,13,12,13,14,15,14,15,16,17,16,17,18,19,18,
%U A068639 19,18,19,18,19,20,21,20,21,22,23,22,23,24,25,24,25,24,25,24,25,26,27,26
%N A068639 a(0) = 0, a(n) = a(n-1) + (-1)^p(n) for n >= 1, where p(n) = highest power of 2 dividing n.
%H A068639 Paolo Xausa, <a href="/A068639/b068639.txt">Table of n, a(n) for n = 0..10000</a>
%H A068639 J.-P. Allouche and Jeffrey Shallit, <a href="http://www.math.jussieu.fr/~allouche/kreg2.ps">The Ring of k-regular Sequences, II</a>
%H A068639 J.-P. Allouche and Jeffrey Shallit, <a href="https://doi.org/10.1016/S0304-3975(03)00090-2">The ring of k-regular sequences, II</a>, Theoret. Computer Sci., 307 (2003), 3-29.
%H A068639 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H A068639 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%F A068639 a(n) = (n+2*A065359(n))/3; a(n) is asymptotic to n/3. - _Benoit Cloitre_, Oct 04 2003
%F A068639 From _Ralf Stephan_, Oct 17 2003: (Start)
%F A068639 a(0)=0, a(2n) = -a(n) + n, a(2n+1) = -a(n) + n + 1.
%F A068639 a(n) = (1/2) * (A050292(n) + A065359(n)).
%F A068639 G.f.: (1/2) * 1/(1-x) * Sum_{k>=0} (-1)^k*t/(1-t^2) where t=x^2^k. (End)
%F A068639 a(0)=0 then a(n) = ceiling(n/2)-a(n-ceiling(n/2)). - _Benoit Cloitre_, May 03 2004
%t A068639 A068639[n_] := (n + 2*Total[(-1)^Range[0, Max[0, BitLength[n] - 1]]*Reverse[IntegerDigits[n, 2]]])/3;
%t A068639 Array[A068639, 101, 0] (* or *)
%t A068639 Join[{0}, Accumulate[(-1)^IntegerExponent[Range[100], 2]]] (* _Paolo Xausa_, Jun 05 2025 *)
%o A068639 (PARI) a(n)=if(n<1,0,ceil(n/2)-a(n-ceil(n/2)))
%Y A068639 Cf. A050292, A065359, A087733.
%K A068639 nonn,easy
%O A068639 0,5
%A A068639 _N. J. A. Sloane_, Oct 01 2003
%E A068639 More terms from _John W. Layman_ and _Robert G. Wilson v_, Oct 02 2003