Given $n$ balls, all of which are initially in the first of $n$ numbered boxes, $a(n)$ is the number of steps required to get one ball in each box when a step consists of moving to the next box every second ball from the highest-numbered box that has more than one ball.


Not so long ago I proposed this sequence to the OEIS, where during the discussion [**Jon E. Schoenfield**](https://oeis.org/wiki/User:Jon_E._Schoenfield) proposed a formula for $n=2^k$ (already proven [here](https://mathoverflow.net/a/432747/231922)), as well as the following recurrent formula:


$$a(n)=\frac{n(n-1)}{2}-b(n)$$
$$b(n)=[n>3](b\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+c\left(\left\lceil\frac{n}{2}\right\rceil-2\right)+\left\lfloor\frac{n}{2}\right\rfloor-1)$$


Here $c(n)$ is [A181132](https://oeis.org/A181132), i.e., $c(0)=0$; thereafter $c(n) = $ total number of $0$'s in binary expansions of $1, \cdots, n$.


It looks very likely that this formula is correct. To verify it one may use this PARI prog:



```
a(n)=my(A, B, v); v=vector(n, i, 0); v[1]=n; A=0; while(v[n]==0, B=n; while(v[B]<2, B--); v[B+1]+=v[B]\2; v[B]-=v[B]\2; A++); A
c(n)=n + sum(k=1, n, logint(k, 2) - hammingweight(k))
b(n)=if(n>3, b(n\2) + c(ceil(n/2) - 2) + n\2 - 1)
a1(n)=n*(n-1)/2 - b(n)

```

Is there a way to prove it?



Recurrence for the number of steps required to get one ball in each box
Generalise $a$: $a(n, k)$ is the number of steps to perform this process with $n+k$ boxes and balls starting with $n \ge 1$ balls in the first box and one ball each in the next $k$ boxes. Then the original $a(n)$ is $a(n, 0)$.


Clearly $a(1, k) = 0$. If $n > 1$ then we propagate $\lfloor \tfrac n2 \rfloor$ balls right one box, process that tail, and then return to the head. So we have $$a(n, k) = \begin{cases}
0 & \textrm{if } n = 1 \\
1 + a(\lfloor \tfrac n2 \rfloor, 0) + a(\lceil \tfrac n2 \rceil, \lfloor \tfrac n2 \rfloor) & \textrm{if } n > 1 \wedge k = 0 \\
1 + a(1+\lfloor \tfrac n2 \rfloor, k-1) + a(\lceil \tfrac n2 \rceil, k + \lfloor \tfrac n2 \rfloor) & \textrm{if } n > 1 \wedge k > 0
\end{cases}$$




---


If we were to propagate the balls one at a time, it's easy to see that we would require $\frac{n(n-1)}2$ steps. Therefore if we define $b(n, k) = \frac{n(n-1)}2 - a(n, k)$ it counts the total "excess" over one ball per group of the groups propagated. Using the same structural argument as for the cases of $a(n,k)$ we therefore find


$$b(n, k) = \begin{cases}
0 & \textrm{if } n = 1 \\
\lfloor \tfrac n2 \rfloor - 1 + b(\lfloor \tfrac n2 \rfloor, 0) + b(\lceil \tfrac n2 \rceil, \lfloor \tfrac n2 \rfloor) & \textrm{if } n > 1 \wedge k = 0 \\
\lfloor \tfrac n2 \rfloor - 1 + b(1+\lfloor \tfrac n2 \rfloor, k-1) + b(\lceil \tfrac n2 \rceil, k + \lfloor \tfrac n2 \rfloor) & \textrm{if } n > 1 \wedge k > 0
\end{cases}$$


Then the conjecture is equivalent to $$b(\lceil \tfrac n2 \rceil, \lfloor \tfrac n2 \rfloor) \stackrel?= c(\lceil \tfrac n2 \rceil - 2)$$




---


$c(m)$ is noted in <https://oeis.org/A181132> to have recurrence (which I've relabelled)



> 
> $$c(m) = \begin{cases} 0 & \textrm{if } m = 0 \\ c(j) + c(j-1) + j & \textrm{if } m = 2j \\ c(j) + c(j) + j & \textrm{if } m = 2j+1 \end{cases}$$
> 
> 
> 


which we could rewrite as $$c(n) = \begin{cases} 0 & \textrm{if } n = 0 \\
c(\lfloor \tfrac n2 \rfloor) + c(\lceil \tfrac n2 \rceil - 1) + \lfloor \tfrac n2 \rfloor & \textrm{otherwise} \end{cases}$$




---


Finally, we prove by strong induction over $n$ that $$\forall n > 1, k \ge \lfloor \log\_2 n \rfloor - 1 : b(n, k) = c(n - 2)$$


Base cases: $n \in \{2,3\}$. We only ever propagate one ball at a time, so $b(2, k) = b(3, k) = 0$.


Inductive step: let $n \ge 4$ and suppose the given property holds for all $n' < n$. Let $k \ge \lfloor \log\_2 n \rfloor - 1$. Then $$\begin{eqnarray\*}b(n, k) &=& \lfloor \tfrac n2 \rfloor - 1 + b(1+\lfloor \tfrac n2 \rfloor, k-1) + b(\lceil \tfrac n2 \rceil, k + \lfloor \tfrac n2 \rfloor) \\
&=& \lfloor \tfrac n2 \rfloor - 1 + c(\lfloor \tfrac n2 \rfloor - 1) + c(\lceil \tfrac n2 \rceil - 2) \\
&=& c(n - 2)
\end{eqnarray\*}$$ as desired.




---


Going beyond what was asked in the question, this then lets us derive $$b(n) = b(\lfloor \tfrac n2 \rfloor) + c(n-2) - c(\lfloor \tfrac n2 \rfloor - 1)$$ from which, by induction, we have $$b(n) = c(n-1) - \sum\_{a \ge 0} \textrm{A080791}\left(\left\lfloor \frac n{2^a} \right\rfloor - 1\right)$$ where [A080791](https://oeis.org/A080791) is the sequence summed by $c$.


