OFFSET
0,2
COMMENTS
Conjecture: given n balls, all of which are initially in the first of n numbered boxes, a(n-1) is the number of steps of the following process required to move them all to the last box. A step consists of first identifying j, the lowest numbered box which has at least one ball. If it has only one ball then move it to box j+1; otherwise move half its balls rounded down to box j+1 and (unless it's the first box) half its balls rounded down to box j-1. See also A356254. - Mikhail Kurkov, Nov 24 2022
LINKS
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi 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, Svante Janson, and Tsung-Hsi 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.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple generating functions, 2004.
Ralf Stephan, Table of generating functions (ps file).
Ralf Stephan, Table of generating functions (pdf file).
FORMULA
a(n) is asymptotic to 2*n^2 and it seems that a(n) = 2*n^2 + O(n^(3/2)) (where O(n^(3/2))/n^(3/2) is bounded and O(n^(3/2)) < 0). - Benoit Cloitre, Oct 30 2002
G.f.: (1/(1-x)^2) * Sum_{k>=0} t/(1-t) where t = x^2^k. Twice the value of the partial sum of A005187. a(0) = 0, a(2n) = a(n) + a(n-1) + 4*n^2 + 2*n, a(2n+1) = 2*a(n) + 4*n^2 + 6*n + 2. - Ralf Stephan, Sep 12 2003
a(n) = 2*n*(n+1) - 2*A000788(n) and therefore asymptotically a(n) = 2*n^2 - n*log_2(n) + O(n). - Peter J. Taylor, Dec 21 2022
PROG
(PARI) {a(n) = sum( k=0, n, -valuation( polcoeff( pollegendre(2*n), 2*k), 2))}
(PARI) a(n)=my(P=pollegendre(2*n)); -sum(k=0, n, valuation(polcoeff(P, 2*k), 2)) \\ Charles R Greathouse IV, Apr 12 2012
CROSSREFS
KEYWORD
nonn
AUTHOR
Michael Somos, Oct 25 2002
STATUS
approved