login
Partial sums of A005187.
5

%I #19 Jan 25 2022 13:10:11

%S 0,1,4,8,15,23,33,44,59,75,93,112,134,157,182,208,239,271,305,340,378,

%T 417,458,500,546,593,642,692,745,799,855,912,975,1039,1105,1172,1242,

%U 1313,1386,1460,1538,1617,1698,1780,1865,1951,2039,2128,2222,2317,2414

%N Partial sums of A005187.

%H Alois P. Heinz, <a href="/A122247/b122247.txt">Table of n, a(n) for n = 0..10000</a>

%H Hsien-Kuei Hwang, Svante Janson and Tsung-Hsi Tsai, <a href="https://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. Also <a href="http://algo.stat.sinica.edu.tw/hk/?p=1043">first authors' copy</a>, 2016. See example 6.2.

%F a(n) = Sum_{k=1..n} Sum_{j=0..n} floor(k/2^j).

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

%p b:= proc(n) option remember; `if`(n=0, 0, b(iquo(n, 2))+n) end:

%p a:= proc(n) option remember; `if`(n=0, 0, b(n)+a(n-1)) end:

%p seq(a(n), n=0..50); # _Alois P. Heinz_, Jan 25 2022

%t Accumulate[Table[2n-Count[IntegerDigits[2 n,2],1],{n,0,70}]] (* _Harvey P. Dale_, Oct 22 2011 *)

%Y Cf. A005187 (first differences).

%K easy,nonn

%O 0,3

%A _Paul Barry_, Aug 27 2006