OFFSET
0,2
COMMENTS
a(n) = A001855(n) + 1 for n > 0;
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.
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
KEYWORD
nonn,easy,base
AUTHOR
Reinhard Zumkeller, May 01 2003
STATUS
approved