A083652 Sum of lengths of binary expansions of 0 through n.

1, 2, 4, 6, 9, 12, 15, 18, 22, 26, 30, 34, 38, 42, 46, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120, 125, 130, 136, 142, 148, 154, 160, 166, 172, 178, 184, 190, 196, 202, 208, 214, 220, 226, 232, 238, 244, 250, 256, 262, 268, 274, 280, 286, 292

Offset

0,2

Comments

a(n) = A001855(n) + 1 for n > 0;

a(0) = A070939(0)=1, n > 0: a(n) = a(n-1) + A070939(n).

A030190(a(k))=1; A030530(a(k)) = k + 1.

Partial sums of A070939. - Hieronymus Fischer, Jun 12 2012

Young writes "If n = 2^i + k [...] the maximum is (i+1)(2^i+k)-2^{i+1}+2." - Michael Somos, Sep 25 2012

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.

Hsien-Kuei Hwang, S. Janson, and T.-H. 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; DOI: 10.1145/3127585.

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 36.

Alfred Young, The Maximum Order of an Irreducible Covariant of a System of Binary Forms, Proc. Roy. Soc. 72 (1903), 399-400 = The Collected Papers of Alfred Young, 1977, 136-137.

Index entries for sequences related to binary expansion of n

Formula

a(n) = 2 + (n+1)*ceiling(log_2(n+1)) - 2^ceiling(log_2(n+1)).

G.f.: g(x) = 1/(1-x) + (1/(1-x)^2)*Sum_{j>=0} x^2^j. - Hieronymus Fischer, Jun 12 2012; corrected by Ilya Gutkovskiy, Jan 08 2017

a(n) = A123753(n) - n. - Peter Luschny, Nov 30 2017

Example

G.f. = 1 + 2*x + 4*x^2 + 6*x^3 + 9*x^4 + 12*x^5 + 15*x^6 + 18*x^7 + 22*x^8 + ...

Mathematica

Accumulate[Length/@(IntegerDigits[#, 2]&/@Range[0, 60])] (* Harvey P. Dale, May 28 2013 *)
a[n_] := (n + 1) IntegerLength[n + 1, 2] - 2^IntegerLength[n + 1, 2] + 2; Table[a[n], {n, 0, 58}] (* Peter Luschny, Dec 02 2017 *)

Prog

(Haskell)
a083652 n = a083652_list !! n
a083652_list = scanl1 (+) a070939_list
-- Reinhard Zumkeller, Jul 05 2012
(PARI) {a(n) = my(i); if( n<0, 0, n++; i = length(binary(n)); n*i - 2^i + 2)}; /* Michael Somos, Sep 25 2012 */
(PARI) a(n)=my(i=#binary(n++)); n*i-2^i+2 \\ equivalent to the above
(Python)
def A083652(n):
    s, i, z = 1, n, 1
    while 0 <= i: s += i; i -= z; z += z
    return s
print([A083652(n) for n in range(0, 59)]) # Peter Luschny, Nov 30 2017
(Python)
def A083652(n): return 2+(n+1)*(m:=(n+1).bit_length())-(1<<m) # Chai Wah Wu, Mar 01 2023

Crossrefs

Cf. A000120, A007088, A023416, A059015, A070939 (base 2), A123753.

A296349 is an essentially identical sequence.

Sequence in context: A130240 A143118 A162800 * A296349 A325544 A118103

Adjacent sequences: A083649 A083650 A083651 * A083653 A083654 A083655

Keyword

nonn,easy,base

Author

Reinhard Zumkeller, May 01 2003

Status

approved