|
%I #36 Apr 21 2024 22:11:37
%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.
%K nonn
%O 1,3
%A _Mikhail Kurkov_, Oct 15 2022 [verification needed]
|
