|
%I #17 May 04 2023 17:53:22
%S 0,1,2,7,15,28,52,97,185,358,702,1387,2755,5488,10952,21877,43725,
%T 87418,174802,349567,699095,1398148,2796252,5592457,11184865,22369678,
%U 44739302,89478547,178957035,357914008,715827952
%N a(n)=a(n-2)+2^(n-1)+5 for n>3, a(0..3)=(0,1,2,7).
%C 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).
%C 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.
%C The BRIDGE transform can be generalized to a nonincreasing sequence as given as PARI code. (Notice the vecsort() instruction.)
%H Harvey P. Dale, <a href="/A147672/b147672.txt">Table of n, a(n) for n = 0..1000</a>
%H National Science Teachers Association, <a href="https://www.math.uni-bielefeld.de/~sillke/PUZZLES/quantum/bridgarc.html">Quantum CyberTeaser Archive #B205, May/June 1997</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3, -1, -3, 2).
%F 2^(n-1) <= a(n) < 2^n for n>0.
%F 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
%e 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).
%t nxt[{n_,a_,b_}]:={n+1,b,a+2^n+5}; Join[{0,1},NestList[nxt,{3,2,7},30][[;;,2]]] (* or *) LinearRecurrence[ {3,-1,-3,2},{0,1,2,7,15,28},40] (* _Harvey P. Dale_, May 04 2023 *)
%o (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] ))) }
%o A147672 = BRIDGE( vector(30,n,2^(n-1)) )
%Y Cf. A147673.
%K nonn
%O 0,3
%A _M. F. Hasler_, Nov 10 2008
|
