A078476 Time taken to get n people from one side of a bridge to the other where (a) the only flashlight must be carried when crossing; (b) only one or two people may cross at the same time; (c) a pair crosses at the speed of the slowest member; and (d) the k-th person's speed requires k seconds to cross the bridge.

1, 2, 6, 11, 16, 22, 28, 35, 42, 50, 58, 67, 76, 86, 96, 107, 118, 130, 142, 155, 168, 182, 196, 211, 226, 242, 258, 275, 292, 310, 328, 347, 366, 386, 406, 427, 448, 470, 492, 515, 538, 562, 586, 611, 636, 662, 688, 715, 742, 770, 798, 827, 856, 886, 916, 947

Offset: 1

Author

Henry Bottomley, Jan 03 2003

Keywords

• nonn
• easy

Comments

Quasipolynomial of order 2. - Charles R Greathouse IV, Mar 26 2013

Examples

			a(5)=16 since one of the fastest ways is for 1&2 to cross (time 2), 1 to return (1), 4&5 to cross (5), 2 to return (2), 1&3 to cross (3), 1 to return (1) and 1&2 to cross (2) for a total time of 2+1+5+2+3+1+2=16.
		

Links

• Torsten Sillke, Crossing the bridge.
• Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).

Programs

PARI

a(n)=n^2\4+3*n-5 \\ Charles R Greathouse IV, Mar 26 2013

Formula

For n>1: a(n)=n^2/4+3n-5+((-1)^n-1)/8.

G.f.: x*(1+2*x^2+x^3-3*x^4)/((1-x)^3*(1+x)). [Colin Barker, Jun 07 2012]

Contribution from Denis Borris, Mar 26 2013: (Start)

n is even: a(n) = (n^2 + 12n - 20) / 4.

n is odd : a(n) = (n^2 + 12n - 21) / 4.

(End)