A122247 Partial sums of A005187.

0, 1, 4, 8, 15, 23, 33, 44, 59, 75, 93, 112, 134, 157, 182, 208, 239, 271, 305, 340, 378, 417, 458, 500, 546, 593, 642, 692, 745, 799, 855, 912, 975, 1039, 1105, 1172, 1242, 1313, 1386, 1460, 1538, 1617, 1698, 1780, 1865, 1951, 2039, 2128, 2222, 2317, 2414

Offset: 0

Author

Paul Barry, Aug 27 2006

Keywords

• easy
• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000
• Hsien-Kuei Hwang, Svante Janson and Tsung-Hsi 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. Also first authors' copy, 2016. See example 6.2.

Crossrefs

Cf. A005187 (first differences).

Programs

Maple

b:= proc(n) option remember; `if`(n=0, 0, b(iquo(n, 2))+n) end:
a:= proc(n) option remember; `if`(n=0, 0, b(n)+a(n-1)) end:
seq(a(n), n=0..50);  # Alois P. Heinz, Jan 25 2022

Mathematica

Accumulate[Table[2n-Count[IntegerDigits[2 n,2],1],{n,0,70}]] (* Harvey P. Dale, Oct 22 2011 *)

Formula

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

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