A318271 The optimum crossing time for the Bridge and Torch problem, given that the crossing times for the group's members are given by the n-th partition in A026791.

1, 1, 2, 3, 2, 3, 5, 4, 3, 2, 4, 7, 6, 5, 5, 4, 3, 5, 9, 8, 7, 6, 6, 6, 5, 6, 4, 3, 6, 11, 10, 9, 8, 8, 7, 7, 8, 7, 7, 6, 7, 5, 4, 7, 13, 12, 11, 10, 10, 9, 9, 9, 8, 7, 8, 9, 8, 8, 7, 10, 8, 8, 6, 5, 4, 8, 15, 14, 13, 12, 12, 11, 11, 11, 10, 9, 10, 10, 9, 8, 9

Offset

1,3

Links

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

User baseman101, The Bridge and Torch Problem, Programming Puzzles & Code Golf Stack Exchange.

Wikipedia, Bridge and torch problem.

Example

When the crossing times are [1,2,5,10], the minimum total time for the group to cross is 17 minutes:
  (2m)  1 and 2 cross,
  (1m)  1 returns,
  (10m) 5 and 10 cross,
  (2m)  2 returns,
  (2m)  1 and 2 cross.
+----+--------------------+------+
|  n | Crossing times     | a(n) |
+----+--------------------+------+
|  1 | [1]                |  1   |
|  2 | [1, 1]             |  1   |
|  3 | [2]                |  2   |
|  4 | [1, 1, 1]          |  3   |
|  5 | [1, 2]             |  2   |
|  6 | [3]                |  3   |
|  7 | [1, 1, 1, 1]       |  5   |
|  8 | [1, 1, 2]          |  4   |
|  9 | [1, 3]             |  3   |
| 10 | [2, 2]             |  2   |
| 11 | [4]                |  4   |
| 12 | [1, 1, 1, 1, 1]    |  7   |
| 13 | [1, 1, 1, 2]       |  6   |
| 14 | [1, 1, 3]          |  5   |
| 15 | [1, 2, 2]          |  5   |
| 16 | [1, 4]             |  4   |
| 17 | [2, 3]             |  3   |
| 18 | [5]                |  5   |
| 19 | [1, 1, 1, 1, 1, 1] |  9   |
| 20 | [1, 1, 1, 1, 2]    |  8   |
| 21 | [1, 1, 1, 3]       |  7   |
| 22 | [1, 1, 2, 2]       |  6   |
| 23 | [1, 1, 4]          |  6   |
| 24 | [1, 2, 3]          |  6   |
| 25 | [1, 5]             |  5   |
| 26 | [2, 2, 2]          |  6   |
| 27 | [2, 4]             |  4   |
| 28 | [3, 3]             |  3   |
| 29 | [6]                |  6   |
+----+--------------------+------+

Prog

(Julia)
function BT(p)
    n = length(p)
    p[end] = -(sum(p) + (n > 2 ? (n-3) * p[1] : 0))
    if n >= 3
        q = 2p[2] - p[1]; tog = false
        for k in n-1:-1:1
            (tog = ~tog) && p[k] > q ? p[k] -= q : p[k] = 0
        end
    end
-sum(p) end
[BT(p) for n in 1:9 for p in A026791(n)] |> println # Peter Luschny, Oct 18 2019

Crossrefs

Cf. A026791, A078476.

Sequence in context: A306196 A052369 A110976 * A236483 A266714 A151570

Adjacent sequences: A318268 A318269 A318270 * A318272 A318273 A318274

Keyword

nonn,nice

Author

Peter Kagey, Aug 22 2018

Extensions

Terms a(45) and beyond added using Erwan's program from CodeGolf StackExchange by Andrey Zabolotskiy, Oct 18 2019

Status

approved