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.


I conjecture that for $n=2^k$ ($k>0$) we have
$$a(n)=\frac{n(n-k+1)}{2}-1$$


To verify given conjecture 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

```

Is there a way to prove it?


I would also like to know if a closed form or recurrence is possible for $a(n)$ in general.



Number of steps required to get one ball in each box for $n=2^k$
The reason is that for $n=2^k$ the following recursion holds:  

$a(n)=1+2a(n/2)+(n/2-1)n/2$.  

To see why this holds, notice that first you split the $n$ balls into two groups of $n/2$, one group in the first box, the other in the second.  

After that, you do $a(n/2)$ steps for the balls in the second box.  

Then, you do $a(n/2)$ steps for the balls in the first box, except that you need to move all but one ball (which stays in the first box) $n/2$ positions farther.  

In these latter steps, only one ball moves each time.  

Once you have the recursion, it is straight-forward to verify your formula.


