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.

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.