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

Author

Mikhail Kurkov, Oct 15 2022

Keywords

• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

Cf. A000217, A001855, A181132.

Programs

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

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