|
|
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.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|