0
$\begingroup$

Let $\operatorname{wt}(n)$ be A000120, i.e., number of $1$'s in binary expansion of $n$ (or the binary weight of $n$).

Then we have an integer sequence given by $$a(n)=n(n+1)-\sum\limits_{k=0}^{n}\operatorname{wt}(k)$$

Given $n$ balls, all of which are initially in the first of $n$ numbered boxes, $b(n)$ is the number of steps required to get $n$ balls in the last box when a step consists of moving to the next box every second ball and also moving (except for the first box) to the previous box the same number of balls from the lowest-numbered box that has at least one ball (if we have only one ball in a box, then we just move it to the next box).

In other words, we initially choose the lowest-numbered box that has at least one ball and:

  1. if there is only one ball in the box, we just move it to the next box.
  2. if we have selected the first box and number of balls is bigger than $1$, we simply move the half rounded down balls to the next box.
  3. if we have selected any other box and number of balls is bigger than $1$, we simply move the half rounded down balls to the next box and move the half rounded down balls to the previous box.

Using notation described by Peter J. Taylor in comments, we have:

If $d_t(i)$ denotes the number of balls in box $i$ after step $t$ we have $d_0(i)=n[i=1]$ using Iverson brackets; let $j$ be the number of the lowest-numbered box that has at least one ball, then we have:

  1. if $d_t(j)=1$, then $d_{t+1}(j)=d_t(j)-1$ and $d_{t+1}(j+1)=d_t(j+1)+1$.
  2. if $j=1$ and $d_t(j)>1$, then $d_{t+1}(j)=d_t(j)-\left\lfloor\frac{d_t(j)}{2}\right\rfloor$ and $d_{t+1}(j+1)=d_t(j+1)+\left\lfloor\frac{d_t(j)}{2}\right\rfloor$.
  3. if $j>1$ and $d_t(j)>1$, then $d_{t+1}(j)=d_t(j)-2\left\lfloor\frac{d_t(j)}{2}\right\rfloor$, $d_{t+1}(j+1)=d_t(j+1)+\left\lfloor\frac{d_t(j)}{2}\right\rfloor$ and $d_{t+1}(j-1)=d_t(j-1)+\left\lfloor\frac{d_t(j)}{2}\right\rfloor$.

I conjecture that $b(n)=2a(n-1)$.

One may verify this conjecture using this PARI prog:

a(n)=my(A, B, v); v=vector(n, i, 0); v[1]=n; A=0; while(v[n]!=n, B=1; while(v[B]<1, B++); v[B+1]+=if(v[B]==1,1,v[B]\2); if(B>1,v[B-1]+=v[B]\2); v[B]-=if(v[B]==1,1,(1+(B>1))*(v[B]\2)); A++); A

Is there a way to prove it?

Improve this question
$\endgroup$
13
  • 3
    $\begingroup$ The description of the process is extremely confusing. If $d_t(i)$ denotes the number of balls in box $i$ after step $t$ we have $d_0(i) = n[i=0]$ using Iverson brackets; what is $d_{t+1}(i)$ in terms of $d_t$? $\endgroup$
    – Peter Taylor
    Commented Dec 20, 2022 at 12:04
  • 1
    $\begingroup$ In rereading I think there's an implied "select a box" at the start of the step, which I didn't get first time. I would understand "moving to the next box every second ball" to mean "half rounded down" except that rounding up seems necessary to make sufficient progress. But what does "also moving (except for the first box) to the previous box the same number of balls from the lowest-numbered box that has at least one ball" mean e.g. in cases where the lowest numbered non-empty box doesn't have enough balls in it? $\endgroup$
    – Peter Taylor
    Commented Dec 21, 2022 at 0:07
  • 3
    $\begingroup$ I think it's off scope to suggest "please write a program in PARI" instead of properly explaining your iteration mathematically and precisely. $\endgroup$
    – kodlu
    Commented Dec 21, 2022 at 2:43
  • 1
    $\begingroup$ Thank you, that's much clearer. Directly from OEIS we have $a(n) = 2n(n+1) - 2\sum_{k=0}^n h(k)$ where $h$ is the Hamming weight, and that seems potentially a more useful starting point than the balls and boxes process. $\endgroup$
    – Peter Taylor
    Commented Dec 21, 2022 at 8:52
  • 1
    $\begingroup$ In fact, the result is already in OEIS, hidden away in Ralf Stephan's comment on A077071. $\endgroup$
    – Peter Taylor
    Commented Dec 21, 2022 at 9:47

0

Reset to default

You must log in to answer this question.