|
Search: id:A136445
|
|
|
| A136445 |
|
Size of the BDD for the hidden weighted bit function, with the variables in their natural ordering. |
|
+0
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; listen)
|
|
|
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: A161618 A157933 A013915 this_sequence A052989 A022403 A082550
Adjacent sequences: A136442 A136443 A136444 this_sequence 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
|
|
|
Search completed in 0.002 seconds
|
