%I #12 Jul 02 2023 17:58:22

%S 2,5,17,47,119,287,671,1535,3455,7679,16895,36863,79871,172031,368639,

%T 786431,1671167,3538943,7471103,15728639,33030143,69206015,144703487,

%U 301989887,629145599,1308622847,2717908991,5637144575,11676942335

%N Number of 2-input gates used to synthesize parity function in disjunctive normal form (DNF) with n inputs.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (5, -8, 4).

%F a(n) = 3*n * 2^(n-2) - 1 for n>1.

%F G.f.: x*(2-5*x+8*x^2-6*x^3)/((1-x)*(1-2*x)^2). [_Colin Barker_, Apr 17 2012]

%e a(7) = 21 * 32 - 1 = 671.

%t Rest[CoefficientList[Series[x (2-5x+8x^2-6x^3)/((1-x)(1-2x)^2),{x,0,30}],x]] (* _Harvey P. Dale_, Feb 18 2013 *)

%K easy,nonn

%O 1,1

%A Nikolay S. Maltchev (nikolay(AT)maltchev.com), Sep 25 2002