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

%I #41 Jul 02 2023 16:28:33

%S 1,3,5,11,17,35,53,107,161,323,485,971,1457,2915,4373,8747,13121,

%T 26243,39365,78731,118097,236195,354293,708587,1062881,2125763,

%U 3188645,6377291,9565937,19131875,28697813,57395627,86093441,172186883

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

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

%H Harry J. Smith, <a href="/A060647/b060647.txt">Table of n, a(n) for n = 0..500</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1, 3, -3).

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

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

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

%F G.f.: (1+2*z-z^2)/((1-z)*(1-3*z^2)). - _Emeric Deutsch_, Nov 18 2002

%F a(n) = (sqrt(3))^n(1+2/sqrt(3))+(1-2/sqrt(3))(-sqrt(3))^n-1. - _Paul Barry_, Apr 17 2004

%F 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.

%F 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

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

%p 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:

%p 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

%t 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 *)

%t 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 *)

%t CoefficientList[ Series[(1 + 2x - x^2)/((1 - x)(1 - 3x^2)), {x, 0, 35}], x] (* _Robert G. Wilson v_, Nov 17 2005 *)

%o (PARI) { for (n=0, 500, if (n%2==0, a=2*(3^(n/2)) - 1, m=(n - 1)/2; a=3^m + 3^(m + 1) - 1); write("b060647.txt", n, " ", a); ) } \\ _Harry J. Smith_, Jul 09 2009

%Y For b=2 see A052955.

%Y Cf. A068911.

%K easy,nonn

%O 0,2

%A _Frank Ellermann_, Apr 17 2001

%E More terms from _James A. Sellers_, Apr 19 2001