|
%I #37 Feb 27 2024 04:09:57
%S 3,3,7,10,17,25,40,57,85,121,172,240,335,459,630,856,1160,1564,2105,
%T 2821,3777,5044,6728,8961,11926,15854,21066,27972,37127,49258,65336,
%U 86636,114862,152256,201800,267436,354394,469591,622205,824379,1092211
%N Size of the BDD for the hidden weighted bit function, with the variables in their natural ordering.
%D D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.4.
%H T. D. Noe, <a href="/A136445/b136445.txt">Table of n, a(n) for n = 1..1000</a>
%H Beate Bollig, Martin Löbbing, Martin Sauerhoff and Ingo Werner, <a href="http://www.numdam.org/item/?id=ITA_1999__33_2_103_0">On the complexity of the hidden weighted bit function for various BDD models</a>, Theoretical Informatics and Applications, 33 (1999), 103-115, Theorem 4.4.
%H Randal E. Bryant, <a href="https://www.cs.cmu.edu/~bryant/pubdir/ieeetc91.pdf">On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication</a>, IEEE Transactions on Computers C-40 (1991), 205-213.
%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,0,-3,-2,2,2,0,-1).
%F 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
%F 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
%e 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
%t 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 *)
%t 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 *)
%o (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
%Y Cf. A137202.
%K nonn,easy
%O 1,1
%A _Don Knuth_, Apr 04 2008
%E Bryant reference added by _Don Knuth_, Apr 23 2008
%E Extension from _T. D. Noe_, Dec 10 2008
|
