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

2, 5, 17, 47, 119, 287, 671, 1535, 3455, 7679, 16895, 36863, 79871, 172031, 368639, 786431, 1671167, 3538943, 7471103, 15728639, 33030143, 69206015, 144703487, 301989887, 629145599, 1308622847, 2717908991, 5637144575, 11676942335

Offset: 1

Author

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

Keywords

• easy
• nonn

Examples

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

Links

• Index entries for linear recurrences with constant coefficients, signature (5, -8, 4).

Programs

Mathematica

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 *)

Formula

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

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