A033156 a(1) = 1; for m >= 2, a(n) = a(n-1) + floor(a(n-1)/(n-1)) + 2.

1, 4, 8, 12, 17, 22, 27, 32, 38, 44, 50, 56, 62, 68, 74, 80, 87, 94, 101, 108, 115, 122, 129, 136, 143, 150, 157, 164, 171, 178, 185, 192, 200, 208, 216, 224, 232, 240, 248, 256, 264, 272, 280, 288, 296, 304, 312, 320, 328, 336, 344, 352, 360, 368, 376, 384, 392, 400, 408

Offset: 1

Author

N. J. A. Sloane, Jun 05 2002

Keywords

• nonn

Links

• Harvey P. Dale, Table of n, a(n) for n = 1..1000
• 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.
• Haomin Li, Computing a Basis for an Integer Lattice, Master's Thesis, Univ. of Waterloo (Ontario, Canada 2022).
• M. A. Nyblom, Some curious sequences involving floor and ceiling functions, Am. Math. Monthly 109 (#6, 200), 559-564, Th. 3.1.
• Ralf Stephan, Some divide-and-conquer sequences ...
• Ralf Stephan, Table of generating functions

Crossrefs

Cf. A123753.

Programs

Maple

A033156 := proc(n) option remember; if n=1 then 1 else A033156(n-1)+floor(A033156(n-1)/(n-1))+2; fi; end;

Mathematica

a[n_] := n (2 + IntegerLength[n, 2]) - 2^IntegerLength[n, 2];
Table[a[n], {n, 1, 59}] (* Peter Luschny, Dec 02 2017 *)
nxt[{n_,a_}]:={n+1,a+Floor[a/n]+2}; NestList[nxt,{1,1},60][[All,2]] (* Harvey P. Dale, Nov 03 2020 *)

Python

def A033156(n):
    s, i, z = 2*n-1, n-1, 1
    while 0 <= i: s += i; i -= z; z += z
    return s
print([A033156(n) for n in range(1, 60)]) # Peter Luschny, Nov 30 2017

Python

def A033156(n): return n*(2+(m:=(n-1).bit_length()))-(1<Chai Wah Wu, Mar 29 2023

Formula

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

a(n) = n + a(floor(n/2)) + a(ceiling(n/2)) = n + min{a(k) + a(n-k):0 < k < n} = n + A003314(n). - Henry Bottomley, Jul 03 2002

A001855(n) + 2n-1. a(n) = b(n)+1 with b(0)=0, b(2n) = b(n) + b(n-1) + 2n + 2, b(2n+1) = 2b(n) + 2n + 3. - Ralf Stephan, Oct 24 2003

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