A136445 Size of the BDD for the hidden weighted bit function, with the variables in their natural ordering.
3, 3, 7, 10, 17, 25, 40, 57, 85, 121, 172, 240, 335, 459, 630, 856, 1160, 1564, 2105, 2821, 3777, 5044, 6728, 8961, 11926, 15854, 21066, 27972, 37127, 49258, 65336, 86636, 114862, 152256, 201800, 267436, 354394, 469591, 622205, 824379, 1092211
Offset: 1
Examples
By the first formula: a(9) = (56*A001608(11)+77*A001608(10) + 47*A001608(9))/23 - floor(9^2/4) - floor((7*9+1)/3) + (9 mod 2) - 10 = 135 - 20 - 21 + 1 - 10 = 85. - _Bruno Berselli_, Jan 31 2013
References
- D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.4.
Links
- T. D. Noe, Table of n, a(n) for n = 1..1000
- Beate Bollig, Martin Löbbing, Martin Sauerhoff and Ingo Werner, On the complexity of the hidden weighted bit function for various BDD models, Theoretical Informatics and Applications, 33 (1999), 103-115, Theorem 4.4.
- Randal E. Bryant, On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication, IEEE Transactions on Computers C-40 (1991), 205-213.
- Index entries for linear recurrences with constant coefficients, signature (1,2,0,-3,-2,2,2,0,-1).
Crossrefs
Cf. A137202.
Programs
-
Magma
I:=[3,3,7,10,17,25,40,57,85]; [n le 9 select I[n] else Self(n-1)+2*Self(n-2)-3*Self(n-4)-2*Self(n-5)+2*Self(n-6)+2*Self(n-7)-Self(n-9): n in [1..45]]; // Vincenzo Librandi, Aug 09 2015
-
Mathematica
p[n_] := n*Sum[Binomial[k, n-2*k]/k, {k, 1, n/2}]; a[n_] := (56*p[n+2] + 77*p[n+1] + 47*p[n])/23 - Floor[n^2/4] - Floor[(7*n+1)/3] + Mod[n, 2] - 10; Table[a[n], {n, 1, 41}] (* Jean-François Alcover, Jan 31 2013 *) LinearRecurrence[{1, 2, 0, -3, -2, 2, 2, 0, -1}, {3, 3, 7, 10, 17, 25, 40, 57, 85}, 50] (* Vincenzo Librandi, Aug 09 2015 *)
Formula
a(n) = (56*P(n+2)+77*P(n+1)+47*P(n))/23 - floor(n^2/4) - floor((7*n+1)/3) + (n mod 2) - 10, where P = A001608. - Don Knuth, Dec 09 2008
G.f.: -x*(x^8+x^7-2*x^6-3*x^5-2*x^4+3*x^3+2*x^2-3) / ((x-1)^3*(x+1)*(x^2+x+1)*(x^3+x^2-1)). - Colin Barker, Jan 29 2013