A356254 - OEIS

%I #40 Oct 20 2024 21:13:24

%S 0,1,3,5,9,13,18,23,31,39,47,56,67,78,91,103,119,135,150,167,185,203,

%T 223,243,266,289,313,337,364,391,420,447,479,511,541,574,607,640,675,

%U 711,749,787,826,865,907,949,993,1036,1083,1130,1177,1225,1275,1325,1377

%N 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.

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

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

%H Peter J. Taylor, <a href="https://mathoverflow.net/a/433195/231922">Recurrence for the number of steps required to get one ball in each box</a>, answer to question on Mathoverflow.

%F If n = 2^k, then a(n) = (n/2)*(n + 1 - k) - 1. - _Jon E. Schoenfield_, Oct 17 2022

%F 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

%e For n = 5, the number of balls in each box at each step is as follows:

%e .

%e        |      Boxes

%e   Step | #1 #2 #3 #4 #5

%e   -----+-------------------

%e      0 |  5

%e      1 |  3  2

%e      2 |  3  1  1

%e      3 |  2  2  1

%e      4 |  2  1  2

%e      5 |  2  1  1  1

%e      6 |  1  2  1  1

%e      7 |  1  1  2  1

%e      8 |  1  1  1  2

%e      9 |  1  1  1  1  1

%e .

%e Thus, a(5) = 9.

%o (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

%Y Cf. A000217, A001855, A181132.

%K nonn

%O 1,3

%A _Mikhail Kurkov_, Oct 15 2022