login
This site is supported by donations to The OEIS Foundation.

 

Logo


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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 17 18:24 EST 2019. Contains 329241 sequences. (Running on oeis4.)