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,1

Links

Table of n, a(n) for n=1..29.

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

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]

Example

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

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

Crossrefs

Sequence in context: A215580 A275210 A219554 * A051438 A368756 A148401

Adjacent sequences: A074491 A074492 A074493 * A074495 A074496 A074497

Keyword

easy,nonn

Author

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

Status

approved