login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A083652 Sum of lengths of binary expansions of 0 through n. 14
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 (list; graph; refs; listen; history; text; internal format)
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, 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, 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.

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

CROSSREFS

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

A296349 is an essentially identical sequence.

Sequence in context: A143118 A162800 * A296349 A118103 A185601 A157795

Adjacent sequences:  A083649 A083650 A083651 * A083653 A083654 A083655

KEYWORD

nonn,easy,base

AUTHOR

Reinhard Zumkeller, May 01 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified April 19 23:02 EDT 2018. Contains 302749 sequences. (Running on oeis4.)