OFFSET
1,2
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
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
MAPLE
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 *)
PROG
(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<<m) # Chai Wah Wu, Mar 29 2023
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Jun 05 2002
STATUS
approved