The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A136445 Size of the BDD for the hidden weighted bit function, with the variables in their natural ordering. 3
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,1 REFERENCES 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. 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 Index entries for linear recurrences with constant coefficients, signature (1,2,0,-3,-2,2,2,0,-1). 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 EXAMPLE 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 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 *) PROG (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 CROSSREFS Cf. A137202. Sequence in context: A202873 A157933 A013915 * A326269 A052989 A252750 Adjacent sequences:  A136442 A136443 A136444 * A136446 A136447 A136448 KEYWORD nonn,easy AUTHOR Don Knuth, Apr 04 2008 EXTENSIONS Bryant reference added by Don Knuth, Apr 23 2008 Extension from T. D. Noe, Dec 10 2008 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 16 08:07 EDT 2021. Contains 343940 sequences. (Running on oeis4.)