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 n-i+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.

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

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 n-1, then person n-1 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 drop-off 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(n-1) - 2*a(n-3) + a(n-4) for n > 4. G.f.: x^2*(2+x^2-x^3)/((1-x)^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)\2-1-bitand(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 * A357355 A114885 A049793

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