%I A137202
%S A137202 3,3,5,9,16,23,33,46,63,82,109,139,178,224,282,348,434,531,653,796,
%T A137202 973,1176,1433,1725,2090
%N A137202 Number of nodes in the BDD for the hidden weighted bit function h_n under 
               the best possible ordering of variables.
%C A137202 In this problem we don't consider "complement bits" to shorten the BDD.
%C A137202 The best method presently known to find a(n) takes something like 2.5^n 
               steps.
%D A137202 Beate Bollig, Martin L\"obbing, 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.
%D A137202 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 A137202 D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.4.
%e A137202 For example, when n=8 the smallest BDD is obtained when one tests first 
               x8 (1 node), then x7 (2 nodes), then x1 (4), then x6 (6), then x2 
               (9), then x5 (12), then x4 (8), then x3 (2). The total number of 
               nodes is 46, including the two sink nodes.
%Y A137202 Cf. A136445.
%Y A137202 Sequence in context: A159284 A078028 A104220 this_sequence A146926 A000198 
               A027170
%Y A137202 Adjacent sequences: A137199 A137200 A137201 this_sequence A137203 A137204 
               A137205
%K A137202 nonn
%O A137202 1,1
%A A137202 D. E. Knuth, Apr 23 2008