0,3

BRIDGE transform of A000079(n)=2^n. The BRIDGE transform of an increasing sequence {c(n), n=0,1,2...} is the sequence b() defined as follows: b(0)=0, b(1)=c(0), b(2)=c(1), b(3)=c(0)+c(1)+c(2) and for n>3, b(n)=b(n-2)+c(n-1)+2*c(1)+c(0).

The name comes from the puzzle "Crossing the bridge" (cf. link): If this puzzle is generalized to a group of n people who need c(0),...,c(n-1) minutes to cross the bridge, then b(n) is an upper bound for the optimal solution, conjectured to be optimal, cf. explanations from F. T. Adams-Watters to the SeqFan list, Nov 10 2008.

The BRIDGE transform can be generalized to a nonincreasing sequence as given as PARI code. (Notice the vecsort() instruction.)

National Science Teachers Association, Quantum CyberTeaser Archive #B205, May/June 1997

2^(n-1) <= a(n) < 2^n for n>0.

G.f.: x(1-x+2x^2-x^3-6x^4)/((1+x)(1-2x)(1-x)^2). a(n) = 5n/2 -23/4 +(-1)^n/12 +2^(n+1)/3, n>1. [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Nov 10 2008]

a(4)=15=2+1+8+2+2 is the time required to cross the bridge for a boy, his sister, his father and his mother if they require 1,2,4,8 minutes, respectively, to cross the bridge individually (using the moves B+G,B,M+F,G,B+G).

(PARI) BRIDGE( a )={ local( s=vector(#a), t ); vector( #a, n, t=vecsort( vecextract( a, 2^n-1 )); t[n]+if( n>3, t[1]+2*t[2]+BRIDGE( vecextract( t, 2^(n-2)-1 ))[n-2], if(n==3, t[1]+t[2] ))) }

A147672 = BRIDGE( vector(30, n, 2^(n-1)) )

Cf. A147673.

Sequence in context: A061802 A003452 A000148 this_sequence A095091 A131412 A151998

Adjacent sequences: A147669 A147670 A147671 this_sequence A147673 A147674 A147675

nonn

M. F. Hasler (MHasler(AT)univ-ag.fr), Nov 10 2008