cp's OEIS Frontend

A078903 a(n) = n^2 - Sum_{u=1..n} Sum_{v=1..u} valuation(2*v, 2).

%I A078903 #43 Nov 13 2024 17:15:56
%S A078903 0,0,1,1,2,3,5,5,6,7,9,10,12,14,17,17,18,19,21,22,24,26,29,30,32,34,
%T A078903 37,39,42,45,49,49,50,51,53,54,56,58,61,62,64,66,69,71,74,77,81,82,84,
%U A078903 86,89,91,94,97,101,103,106,109,113,116,120,124,129,129,130,131,133,134
%N A078903 a(n) = n^2 - Sum_{u=1..n} Sum_{v=1..u} valuation(2*v, 2).
%C A078903 This is a fractal generator sequence. Let Fr(m,n) = m*n - a(n); then the graph of Fr(m,n) for 1 <= n <= 4^(m+1) - 3 presents fractal aspects.
%H A078903 Ivan Neretin, <a href="/A078903/b078903.txt">Table of n, a(n) for n = 1..10000</a>
%H A078903 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, preprint, 2016.
%H A078903 Hsien-Kuei Hwang, Svante Janson, Tsung-Hsi Tsai, <a href="http://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms 13:4 (2017), #47.
%H A078903 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences with (relatively) simple generating functions</a>, 2004.
%H A078903 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions (ps file)</a>.
%H A078903 Ralf Stephan, <a href="/A067699/a067699.pdf">Table of generating functions (pdf file)</a>.
%F A078903 a(n) = n^2 - Sum_{k=1..n} A005187(k);
%F A078903 a(n) = n^2 - Sum_{u=1..n} Sum_{v=1..u} A001511(v);
%F A078903 a(n+1) - a(n) = A048881(n).
%F A078903 G.f.: 1/(1-x)^2 * ((x(1+x)/(1-x) - Sum_{k>=0} x^2^k/(1-x^2^k))). - _Ralf Stephan_, Apr 12 2002
%F A078903 a(0) = 0, a(2*n) = a(n) + a(n-1) + n - 1, a(2*n+1) = 2*a(n) + n. Also, a(n) = A000788(n) - n. - _Ralf Stephan_, Oct 05 2003
%e A078903 Fr(1, n) for 1 <= n <= 4^2-3 = 13 gives 1, 2, 2, 3, 3, 3, 2, 3, 3, 3, 2, 2, 1.
%e A078903 Fr(2, n) for 1 <= n <= 4^3-3 = 63 gives 2, 4, 5, 7, 8, 9, 9, 11, 12, 13, 13, 14, 14, 14, 13, 15, 16, 17, 17, 18, 18, 18, 17, 18, 18, 18, 17, 17, 16, 15, 13, 15, 16, 17, 17, 18, 18, 18, 17, 18, 18, 18, 17, 17, 16, 15, 13, 14, 14, 14, 13, 13, 12, 11, 9, 9, 8, 7, 5, 4, 2.
%p A078903 a:= proc(n) option remember; `if`(n=0, 0,
%p A078903       a(n-1)-1+add(i, i=Bits[Split](n)))
%p A078903     end:
%p A078903 seq(a(n), n=1..68);  # _Alois P. Heinz_, Feb 03 2024
%t A078903 Accumulate@Table[DigitCount[n, 2, 1] - 1, {n, 68}] (* _Ivan Neretin_, Sep 07 2017 *)
%o A078903 (PARI) a(n)=n^2-sum(u=1,n,sum(v=1,u,valuation(2*v,2)))
%o A078903 (Magma) [n^2-(&+[ &+[Valuation(2*v,2):v in [1..u]]:u in [1..n]]):n in [1..70]]; //  _Marius A. Burtea_, Oct 24 2019
%o A078903 (Python)
%o A078903 def A078903(n): return (n+1)*n.bit_count()-n+(sum((m:=1<<j)*((k:=n>>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1))>>1)  # _Chai Wah Wu_, Nov 12 2024
%Y A078903 Cf. A078904, A073504.
%Y A078903 Equals (1/2) * A076178(n).
%K A078903 nonn
%O A078903 1,5
%A A078903 _Benoit Cloitre_, Dec 12 2002