A060647 Number of alpha-beta evaluations in a tree of depth n and branching factor b=3.

1, 3, 5, 11, 17, 35, 53, 107, 161, 323, 485, 971, 1457, 2915, 4373, 8747, 13121, 26243, 39365, 78731, 118097, 236195, 354293, 708587, 1062881, 2125763, 3188645, 6377291, 9565937, 19131875, 28697813, 57395627, 86093441, 172186883, 258280325, 516560651, 774840977

Offset: 0

Author

Frank Ellermann, Apr 17 2001

Keywords

• easy
• nonn

Examples

			a(2n+1) = 2*a(2n) + 1, a(15) = a(2*7+1) = 2*a(14) + 1 = 2*4373 + 1 = 8747.
		

References

• P. H. Winston, Artificial Intelligence, Addison-Wesley, 1977, pp. 115-122, (alpha-beta technique).

Links

• Harry J. Smith, Table of n, a(n) for n = 0..500
• Index entries for linear recurrences with constant coefficients, signature (1, 3, -3).

Crossrefs

For b=2 see A052955.

Cf. A068911.

Programs

Maple

A060647 := proc(n,b) option remember: if n mod 2 = 0 then RETURN(2*b^(n/2)-1) else RETURN(b^((n-1)/2) +b^((n+1)/2)-1) fi: end: for n from 0 to 60 do printf(`%d,`, A060647(n,3)) od:
a[0]:=1:a[1]:=3:for n from 2 to 100 do a[n]:=3*a[n-2]+2 od: seq(a[n], n=0..33); # Zerinvary Lajos, Mar 17 2008

Mathematica

f[n_] := Simplify[Sqrt[3]^n(1 + 2/Sqrt[3]) + (1 - 2/Sqrt[3])(-Sqrt[3])^n - 1]; Table[ f[n], {n, 0, 34}] (* or *)
f[n_] := If[ EvenQ[n], 2(3^(n/2)) - 1, 3^((n - 1)/2) + 3^((n + 1)/2) - 1]; Table[ f[n], {n, 0, 34}] (* or *)
CoefficientList[ Series[(1 + 2x - x^2)/((1 - x)(1 - 3x^2)), {x, 0, 35}], x] (* Robert G. Wilson v, Nov 17 2005 *)

PARI

a(n) = { if (n%2==0, 2*(3^(n/2)) - 1, my(m=(n - 1)/2); 3^m + 3^(m + 1) - 1) } \\ Harry J. Smith, Jul 09 2009

Formula

a(2n) = 2*(3^n) - 1, a(2n+1) = 3^n + 3^(n+1) - 1.

Formula for b branches: a(2n) = 2*(b^n)-1, a(2n+1) = b^n+b^(n+1)-1.

a(n) = A068911(n+1) - 1.

G.f.: (1+2*z-z^2)/((1-z)*(1-3*z^2)). - Emeric Deutsch, Nov 18 2002

a(n) = (sqrt(3))^n(1+2/sqrt(3))+(1-2/sqrt(3))(-sqrt(3))^n-1. - Paul Barry, Apr 17 2004

a(2n+1) = 3*a(2n-1) + 2; a(2n) = (a(2n-1) + a(2n+1))/2, with a(1)= 1. See A062318 for case where a(1)= 0.

a(n) = (2^((1+(-1)^n)/2))*(b^((2*n-1+(-1)^n)/4))+((1-(-1)^n)/2)*(b^((2*n+1-(-1)^n)/4))-1, with b=3. - Luce ETIENNE, Aug 30 2014

Extensions

More terms from James Sellers, Apr 19 2001