The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A147672 a(n)=a(n-2)+2^(n-1)+5 for n>3, a(0..3)=(0,1,2,7). 2
0, 1, 2, 7, 15, 28, 52, 97, 185, 358, 702, 1387, 2755, 5488, 10952, 21877, 43725, 87418, 174802, 349567, 699095, 1398148, 2796252, 5592457, 11184865, 22369678, 44739302, 89478547, 178957035, 357914008, 715827952 (list; graph; refs; listen; history; text; internal format)



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 Franklin 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.)


Table of n, a(n) for n=0..30.

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. - R. J. Mathar, 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: A263603 A003452 A000148 * A246790 A289939 A290064

Adjacent sequences:  A147669 A147670 A147671 * A147673 A147674 A147675




M. F. Hasler, Nov 10 2008



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 14 03:42 EDT 2020. Contains 335716 sequences. (Running on oeis4.)