A356254 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.

0, 1, 3, 5, 9, 13, 18, 23, 31, 39, 47, 56, 67, 78, 91, 103, 119, 135, 150, 167, 185, 203, 223, 243, 266, 289, 313, 337, 364, 391, 420, 447, 479, 511, 541, 574, 607, 640, 675, 711, 749, 787, 826, 865, 907, 949, 993, 1036, 1083, 1130, 1177, 1225, 1275, 1325, 1377

Offset

1,3

Comments

The sum of the number of balls being shifted at each step is A000217(n-1).

If the definition were changed to use "lowest-numbered box" instead of "highest-numbered box", then the number of steps would be A001855.

Links

Table of n, a(n) for n=1..55.

Peter J. Taylor, Recurrence for the number of steps required to get one ball in each box, answer to question on Mathoverflow.

Formula

If n = 2^k, then a(n) = (n/2)*(n + 1 - k) - 1. - Jon E. Schoenfield, Oct 17 2022

Define s(n) = floor(n/2) - 1 + s(floor(n/2)) + A181132(ceiling(n/2) - 2) for n > 3, 0 otherwise. Then a(n) = n*(n-1)/2 - s(n). - Jon E. Schoenfield, Oct 18 2022

Example

For n = 5, the number of balls in each box at each step is as follows:
.
       |      Boxes
  Step | #1 #2 #3 #4 #5
  -----+-------------------
     0 |  5
     1 |  3  2
     2 |  3  1  1
     3 |  2  2  1
     4 |  2  1  2
     5 |  2  1  1  1
     6 |  1  2  1  1
     7 |  1  1  2  1
     8 |  1  1  1  2
     9 |  1  1  1  1  1
.
Thus, a(5) = 9.

Prog

(PARI) 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

Crossrefs

Cf. A000217, A001855.

Sequence in context: A036713 A260733 A265429 * A122248 A024403 A129230

Adjacent sequences: A356251 A356252 A356253 * A356255 A356256 A356257

Keyword

nonn

Author

Mikhail Kurkov, Oct 15 2022 [verification needed]

Status

approved