login
Sum of lengths of binary expansions of 0 through n.
18

%I #67 Nov 21 2024 19:18:19

%S 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 95,100,105,110,115,120,125,130,136,142,148,154,160,166,172,178,184,

%U 190,196,202,208,214,220,226,232,238,244,250,256,262,268,274,280,286,292

%N Sum of lengths of binary expansions of 0 through n.

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

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

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

%C Partial sums of A070939. - _Hieronymus Fischer_, Jun 12 2012

%C 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 Reinhard Zumkeller, <a href="/A083652/b083652.txt">Table of n, a(n) for n = 0..10000</a>

%H 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 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 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 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 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

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

%F 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 a(n) = A123753(n) - n. - _Peter Luschny_, Nov 30 2017

%e 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 Accumulate[Length/@(IntegerDigits[#,2]&/@Range[0,60])] (* _Harvey P. Dale_, May 28 2013 *)

%t 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 (Haskell)

%o a083652 n = a083652_list !! n

%o a083652_list = scanl1 (+) a070939_list

%o -- _Reinhard Zumkeller_, Jul 05 2012

%o (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 (PARI) a(n)=my(i=#binary(n++));n*i-2^i+2 \\ equivalent to the above

%o (Python)

%o def A083652(n):

%o s, i, z = 1, n, 1

%o while 0 <= i: s += i; i -= z; z += z

%o return s

%o print([A083652(n) for n in range(0, 59)]) # _Peter Luschny_, Nov 30 2017

%o (Python)

%o def A083652(n): return 2+(n+1)*(m:=(n+1).bit_length())-(1<<m) # _Chai Wah Wu_, Mar 01 2023

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

%Y A296349 is an essentially identical sequence.

%K nonn,easy,base,changed

%O 0,2

%A _Reinhard Zumkeller_, May 01 2003