

A147672


a(n)=a(n2)+2^(n1)+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)



OFFSET

0,3


COMMENTS

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(n2)+c(n1)+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(n1) 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. AdamsWatters 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.)


LINKS

Table of n, a(n) for n=0..30.
National Science Teachers Association, Quantum CyberTeaser Archive #B205, May/June 1997


FORMULA

2^(n1) <= a(n) < 2^n for n>0.
G.f.: x(1x+2x^2x^36x^4)/((1+x)(12x)(1x)^2). a(n) = 5n/2 23/4 +(1)^n/12 +2^(n+1)/3, n>1.  R. J. Mathar, Nov 10 2008


EXAMPLE

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


PROG

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


CROSSREFS

Cf. A147673.
Sequence in context: A263603 A003452 A000148 * A246790 A289939 A290064
Adjacent sequences: A147669 A147670 A147671 * A147673 A147674 A147675


KEYWORD

nonn


AUTHOR

M. F. Hasler, Nov 10 2008


STATUS

approved



