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(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.)
LINKS
Harvey P. Dale, Table of n, a(n) for n = 0..1000
National Science Teachers Association, Quantum CyberTeaser Archive #B205, May/June 1997.
Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,2).
FORMULA
2^(n-1) <= a(n) < 2^n for n>0.
From R. J. Mathar, Nov 10 2008: (Start)
G.f.: x*(1-x+2*x^2-x^3-6*x^4)/((1+x)*(1-2*x)*(1-x)^2).
a(n) = 5*n/2 - 23/4 + (-1)^n/12 + 2^(n+1)/3, n>1. (End)
E.g.f.: (1/12)*( 8*exp(2*x) + 3*(10*x - 23)*exp(x) + 12*(3*x+5) + exp(-x) ). - G. C. Greubel, Dec 09 2025
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).
MATHEMATICA
nxt[{n_, a_, b_}]:={n+1, b, a+2^n+5}; Join[{0, 1}, NestList[nxt, {3, 2, 7}, 30][[;; , 2]]] (* Harvey P. Dale, May 04 2023 *)
(* Alternative: *)
LinearRecurrence[ {3, -1, -3, 2}, {0, 1, 2, 7, 15, 28}, 40] (* Harvey P. Dale, May 04 2023 *)
PROG
(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)) )
(Magma)
A147672:= func< n | n le 1 select n else (2^(n+3) +(-1)^n +30*n -69)/12 >;
[A147672(n): n in [0..40]]; // G. C. Greubel, Dec 09 2025
(SageMath)
def A147672(n): return n if n<2 else (2**(n+3) +(-1)**n +30*n -69)//12
print([A147672(n) for n in range(41)]) # G. C. Greubel, Dec 09 2025
CROSSREFS
KEYWORD
nonn,easy,changed
AUTHOR
M. F. Hasler, Nov 10 2008
STATUS
approved