cp's OEIS Frontend

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

%I A083652 #67 Nov 21 2024 19:18:19
%S A083652 1,2,4,6,9,12,15,18,22,26,30,34,38,42,46,50,55,60,65,70,75,80,85,90,
%T A083652 95,100,105,110,115,120,125,130,136,142,148,154,160,166,172,178,184,
%U A083652 190,196,202,208,214,220,226,232,238,244,250,256,262,268,274,280,286,292
%N A083652 Sum of lengths of binary expansions of 0 through n.
%C A083652 a(n) = A001855(n) + 1 for n > 0;
%C A083652 a(0) = A070939(0)=1, n > 0: a(n) = a(n-1) + A070939(n).
%C A083652 A030190(a(k))=1; A030530(a(k)) = k + 1.
%C A083652 Partial sums of A070939. - _Hieronymus Fischer_, Jun 12 2012
%C A083652 Young writes "If n = 2^i + k [...] the maximum is (i+1)(2^i+k)-2^{i+1}+2." - _Michael Somos_, Sep 25 2012
%H A083652 Reinhard Zumkeller, <a href="/A083652/b083652.txt">Table of n, a(n) for n = 0..10000</a>
%H A083652 Hsien-Kuei Hwang, S. Janson, and T.-H. 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 A083652 Hsien-Kuei Hwang, S. Janson, and T.-H. 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; DOI: 10.1145/3127585.
%H A083652 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, p. 36.
%H A083652 Alfred Young, <a href="http://dx.doi.org/10.1098/rspl.1903.0068">The Maximum Order of an Irreducible Covariant of a System of Binary Forms</a>, Proc. Roy. Soc. 72 (1903), 399-400 = The Collected Papers of Alfred Young, 1977, 136-137.
%H A083652 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A083652 a(n) = 2 + (n+1)*ceiling(log_2(n+1)) - 2^ceiling(log_2(n+1)).
%F A083652 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
%F A083652 a(n) = A123753(n) - n. - _Peter Luschny_, Nov 30 2017
%e A083652 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 + ...
%t A083652 Accumulate[Length/@(IntegerDigits[#,2]&/@Range[0,60])] (* _Harvey P. Dale_, May 28 2013 *)
%t A083652 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 *)
%o A083652 (Haskell)
%o A083652 a083652 n = a083652_list !! n
%o A083652 a083652_list = scanl1 (+) a070939_list
%o A083652 -- _Reinhard Zumkeller_, Jul 05 2012
%o A083652 (PARI) {a(n) = my(i); if( n<0, 0, n++; i = length(binary(n)); n*i - 2^i + 2)}; /* _Michael Somos_, Sep 25 2012 */
%o A083652 (PARI) a(n)=my(i=#binary(n++));n*i-2^i+2 \\ equivalent to the above
%o A083652 (Python)
%o A083652 def A083652(n):
%o A083652     s, i, z = 1, n, 1
%o A083652     while 0 <= i: s += i; i -= z; z += z
%o A083652     return s
%o A083652 print([A083652(n) for n in range(0, 59)]) # _Peter Luschny_, Nov 30 2017
%o A083652 (Python)
%o A083652 def A083652(n): return 2+(n+1)*(m:=(n+1).bit_length())-(1<<m) # _Chai Wah Wu_, Mar 01 2023
%Y A083652 Cf. A000120, A007088, A023416, A059015, A070939 (base 2), A123753.
%Y A083652 A296349 is an essentially identical sequence.
%K A083652 nonn,easy,base
%O A083652 0,2
%A A083652 _Reinhard Zumkeller_, May 01 2003