|
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,1
|
|
|
REFERENCES
| 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.
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
|
|
|
FORMULA
| a_n = (56P_{n+2}+77P_{n+1}+47P_n)/23 - floor(n^2/4) - floor(7n+1)/3) + (n mod 2) - 10, where P_n are the Perrin numbers A001608.
|
|
|
CROSSREFS
| Cf. A137202.
Sequence in context: A202873 A157933 A013915 * A052989 A022403 A082550
Adjacent sequences: A136442 A136443 A136444 * A136446 A136447 A136448
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| D. E. Knuth, Apr 04 2008. Bryant reference added Apr 23 2008. Formula involving Perrin numbers added Dec 09 2008
|
|
|
EXTENSIONS
| Extension from T. D. Noe (noe(AT)sspectra.com), Dec 10 2008
|
| |
|
|
