login
The OEIS is supported by the many generous donors 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
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 11:57 EDT 2024. Contains 371241 sequences. (Running on oeis4.)