cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

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.

Original entry on oeis.org

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

Views

Author

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

Keywords

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

Examples

			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.

Crossrefs

Cf. A162762, A162763 and A162764 for the analog with elevator capacity of C = 2, 3 and 4 persons.

Programs

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

Extensions

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

A162763 Minimal total number of floors an elevator must travel to get n people waiting, respectively, at floors i = 1, 2, ..., n, to their destinations at floors n+1-i (= n, ..., 1), if the elevator can hold at most C = 3 people and starts at floor 1, and no passenger may get off the elevator before reaching his/her destination.

Original entry on oeis.org

0, 2, 4, 6, 8, 10, 12, 18, 22, 27, 31, 35, 39, 47, 53, 60
Offset: 1

Views

Author

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

Keywords

Comments

Equivalently, the distance (or number of edges) a taxicab must drive to transport n people initially standing at km (or vertex) i (= 1, ..., n) to their destinations at km n-i+1, when the taxi can hold at most 3 passengers, and starts at km 1.
In case of odd n, the person at the middle floor (n+1)/2 is already at her destination and does not need to be transported.
The simple algorithm of taking the first C (or [n/2] if less) persons up to their destination, then the last C persons down to their destination, and if not finished, starting over with floor C+1 as new ground floor with n' = n - 2C, yields an upper bound a(n) <= 2n - 2 + C + a(n - 2C) for n > 2C + 1. In the example section we show that this is not optimal for n = 8 and 9, i.e., 2C + 2 and 2C + 3. I conjecture, however, that this upper bound is sharp (i.e., yields the exact result) for all n > 2C + 3. More precisely, I think the assumption of strict inequality for some larger value of n (the smallest such index) gives a proof by contradiction. - M. F. Hasler, May 15 2019
It would be nice to have a program explore all possible/relevant solutions to get an independent check and maybe extension of the given data. - M. F. Hasler, May 15 2019

Examples

			For n = 2, the term a(2) = 2 means the elevator needs to move only 2 floors to transport everyone to his or her destination: the elevator loads one person at floor 1, and moves to floor 2 (up 1 floor), unloads one person and loads another person, then moves back to floor 1 (down 1 floor) and unloads.
From _M. F. Hasler_, May 01 2019: (Start)
Similarly, for n = 3, the person at floor 2 is already at his or her destination, so the elevator can move the person at floor 1 to floor 3 (up 2 floors), then move the person at floor 3 to floor 1 (down 2 floors), whence a(3) = 4.
For n = 4, the elevator must move once up to floor 4 then back down to floor 1 (a total of 3 + 3 floors), with intermediate stops allowing the persons at floors 2 and 3 to enter and get off at their destinations, too: a(4) = 3 + 3 = 6.
The pattern prevails up to n = 7 with a(7) = 6 + 6, where the elevator can hold the persons from floors 1, 2, and 3 simultaneously, and later those from floors 7, 6, and 5 simultaneously.
Beyond this, the limited capacity of the elevator comes into play and requires it to move back and forth between intermediate floors to accomplish the task.
One solution for n = 8 is to take persons 1, 2 and 3, drop off person 3 at floor 6 (moving 5 floors so far), take person 5 down to floor 4 (+ 2 floors), then person 4 to floor 5 and passengers 2 and 1 to their destinations at floor 7 and 8 (+ 4 floors), and finally the persons there down to floor 2 and 1 (+ 7 floors), for a total of a(8) = 5 + 2 + 4 + 7 = 18 floors. A similar solution (inserting an additional floor, where the elevator never has to stop, between 4 and 5) yields a(9) = a(8) + 4 = 22. (End)

Crossrefs

Cf. A162761..A162764 for analogs with capacity C = 1..4.

Programs

  • PARI
    A162763(n,C=3)=2*n-2+if(n>2*C+3, A162763(n-2*C,C)+C,n>2*C+1,2*n-4*C) \\ Proved to be an upper bound, conjectured to be exact (also for other values of C). - M. F. Hasler, May 15 2019

Formula

a(n) = 2n - 2 for n < 2C + 2 = 8, a(n) <= 2n - 2 + C + a(n - 2C) else, see comment for proof. Conjectured to hold with equality for all n except n = 2C + {2, 3} = {8, 9} where a(n) = 4(n - C) - 2 = 4n - 14. - M. F. Hasler, May 15 2019
G.f.: x*(2 + 2*x^6 - 2*x^7 + x^8 - x^9)/((1 - x)^3*(1 + x)*(1 - x + x^2)*(1 + x + x^2)) (conjectured). - M. F. Hasler, May 15 2019

Extensions

Edited by M. F. Hasler, Apr 29 2019

A162762 Minimal number of floors an elevator must move to transport n passengers initially waiting at floors i = 1, ..., n to their destinations, floor n+1-i (= n, ..., 1), if the elevator can transport at most C = 2 persons at a time and starts at floor 1, and no one may get off the elevator before reaching their destination.

Original entry on oeis.org

0, 2, 4, 6, 8, 14, 18, 22, 26, 34, 40, 46, 52, 62, 70, 78, 86
Offset: 1

Views

Author

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

Keywords

Comments

If n is odd, the passenger at floor (n+1)/2 is already at his or her destination and does not need to be transported.
Without the additional constraint that no passenger may (temporarily) get off before reaching his or her destination, there would be smaller solutions, cf. example section and A162761 and A162764. - M. F. Hasler, May 01 2019
An upper bound is provided by the following simple algorithm: Transport the first C persons to the last C floors, then those there down to the first C floors; if not finished, go to floor C+1, consider this as the new ground floor and start over with the same algorithm for n' = n - 2*C. This gives a(n) <= 2n - 2 + C + a(n - 2C) for n > 2C+1; a(n) = 2n - 2 otherwise. For C = 2, this upper bound coincides with all known terms, and yields the same sequence as the g.f. proposed in 2014. For C > 2, it needs an adjustment for n = 2C + {2,3}, cf. A162763 and A162764. - M. F. Hasler, May 15 2019

Examples

			For n = 2, the value a(2) = 2 means the elevator needs to move only 2 floors to transport everyone to their destinations: the elevator loads the person at floor 1 and moves to floor 2 (up 1 floor), unloads and loads one person at floor 2, then moves to floor 1 (down 1 floor) and unloads.
From _M. F. Hasler_, Apr 29 2019: (Start)
Up to n = 5, we have a(n) = 2(n-1) since the passengers on the lower half can all be loaded and moved to their destinations as the elevator travels up to floor n, and then similarly for the remaining passengers as the elevator travels back down to floor 1.
For n = 6 we can take the passengers from floors 1 and 2 to their destinations (moving 5 floors up), then those at floors 6 and 5 (moving 5 floors down), then take the person at floor 3 to floor 4 (+ 2 + 1 floor) and finally take person 4 to floor 3, for a total of a(6) = 14 floors. One can check that there is no faster solution, unless one allows a passenger to get off and on again. E.g., having picked up the persons at floor 6 and 5, one could drop off person 5 at floor 3 (after 5 + 3 floors moved), take person 3 to floor 4 and person 4 to floor 3 (+ 2 floors), and finally person 5 and 6 to floor 2 and 1 (+ 2 floors), for a total of only 5 + 3 + 2 + 2 = 12 < a(6).
For n = 7 we can keep the same plan, inserting an additional floor where the elevator never will stop in the middle between floors 3 and 4. This adds 4 floors to the total distance, for a(7) = 18.
For n = 8, one solution is to go 1 -> 8 -> 1 -> 6 -> 3 (loading and dropping passengers whenever possible) for a total of a(8) = 7 + 7 + 5 + 3 = 22.
Again, the same solution "spaced out" between floor 4 and 5 yields a(9) = 26.
For n = 10, doing 1 -> 10 -> 1 -> 8 -> 3 -> 6 -> 5 yields a(10) = 9 + 9 + 7 + 5 + 3 + 1 = 34. Then again, a(11) = a(10) + 6 = 40.
For n = 12, doing 1 -> 12 -> 1 -> 10 -> 3 -> 8 -> 5 yields a(12) = 11 + 11 + 9 + 7 + 5 + 3 = 46, and a(13) = a(12) + 6 = 52. (End)

Crossrefs

Cf. A162761, A162763 and A162764 for analogs with capacity C = 1, 3 and 4.

Programs

  • PARI
    A162762(n,C=2)=2*n-2+if(n\2>C,A162762(n-2*C)+C) \\ Proved to be an upper bound (cf. comments), only conjectured to be exact for all n. - M. F. Hasler, May 15 2019

Formula

Empirical g.f.: 2*x^2*(x^2-x+1)*(x^3-x-1) / ((x-1)^3*(x+1)*(x^2+1)). - Colin Barker, Jun 21 2014
a(n) = 2n - 2 for n < 2C + 2, a(n) <= 2n - 2 + C + a(n - 2C) otherwise, with equality for all known terms and the above g.f. - M. F. Hasler, May 15 2019

Extensions

Edited by M. F. Hasler, May 01 2019
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.