login
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
OFFSET
1,1
REFERENCES
D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.4.
LINKS
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.
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: A157933 A350394 A013915 * A326269 A052989 A358823
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