

A162761


Minimal total number of floors an elevator must move to transport n people initially waiting at floors i = 1, ..., n to their destination floors ni+1 (= n, ..., 1), when the elevator can hold at most one person at a time and starts at floor 1, and no passenger may get off the elevator before reaching his/her destination.


5



0, 2, 4, 9, 13, 20, 26, 35, 43, 54, 64, 77, 89, 104, 118, 135, 151, 170, 188, 209, 229, 252, 274, 299, 323, 350, 376, 405, 433, 464, 494, 527, 559, 594, 628, 665, 701, 740, 778, 819, 859, 902, 944, 989, 1033, 1080, 1126, 1175, 1223, 1274, 1324, 1377, 1429
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The value a(4) = 9 shows that it is not allowed to unload a passenger before he reaches his destination, cf. examples. This implies that there is no better solution than to transport person 1 to floor n, then person n to floor 1, then person 2 to floor n1, then person n1 to floor 2, etc., which yields a(n) = (Sum_{i=1..floor(n/2)} (n+1  2*i)*2 + 1)  1 (for n > 1), equal to the formula conjectured by C. Barker. It would be interesting to consider the variant of optimal solutions involving temporary dropoff of passengers.  M. F. Hasler, Apr 29 2019


LINKS

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


FORMULA

a(n) = (n^2 + n + (1)^n  3)/2 for n > 1. a(n) = 2*a(n1)  2*a(n3) + a(n4) for n > 4. G.f.: x^2*(2+x^2x^3)/((1x)^3*(1+x)).  Conjectured by Colin Barker, Jun 10 2012, edited and proved by M. F. Hasler, Apr 29 2019


EXAMPLE

For n = 3, the elevator must transport person 1 from floor 1 to floor 3 (2 floors) and then person 3 back to floor 1 (+ 2 more floors to go), whence a(3) = 4.
For n = 4, the limited capacity comes into play. The elevator could transport person 1 to floor 2 (1 floor moved), unload person 1 and take person 2 to floor 3 (+ 1 floor), take person 3 to floor 2 (+ 1 floor), take person 1 to floor 4 (+ 2 floors), and take person 4 to floor 1 (+ 3 floors), for a total of 8 floors moved. It appears that this solution, involving a person getting out and back in again, is excluded, and we need to transport, e.g., 1 > 4, 4 > 1, 2 > 3, 3 > 2, for a total of a(4) = 3 + 3 + 1 + 1 + 1 = 9 floors.


PROG

(PARI) A162761(n)=(n^2+n)\21bitand(n, n>1) \\ M. F. Hasler, Apr 29 2019


CROSSREFS

Cf. A162762, A162763 and A162764 for the analog with elevator capacity of C = 2, 3 and 4 persons.
Sequence in context: A210640 A024925 A162342 * A114885 A049793 A090942
Adjacent sequences: A162758 A162759 A162760 * A162762 A162763 A162764


KEYWORD

nonn,more


AUTHOR

Do Zerg (daidodo(AT)gmail.com), Jul 13 2009


EXTENSIONS

Edited and extended by M. F. Hasler, Apr 29 2019


STATUS

approved



