Build an adding machine using NAND logic gates
31 gates

[created in Logisim]

The standard XOR-gate can be built with four NANDs. Tapping the first NAND provides us with a fairly compact half-adder with inverted carry:
hadder(A,B) =&gt; (sum, iCarry):

X = A^B   

sum = (A^X)^(B^X)
iCarry = X


These can be combined into a 9-gate full adder:
fadder(A,B,C) =&gt; (sum, carry):

DD1 = hadder(A,B)
DD2 = hadder(DD1.sum, C)

sum = DD2.sum
carry = DD1.iCarry ^ DD2.iCarry

These combined yield a naive 36-gate four-bit adder. Not bad.
Now, we inline all modules and perform these optimizations:
delete gates with no output (only the final gate)
0^x =&gt; 1                    (one gate, twice)
1^(1^x) =&gt; 0                (two gates, once)

for a grand total of 31 gates.

Note that the count of splits and NAND-gates are intimately connected: Each 2-input NAND (larger are explicitly forbidden) takes two inputs and produces one output. Each 2-way split (let's assume larger splits are forbidden) takes one input and produces two outputs. Also, there are no unused outputs or floating inputs (let's assume constants are not allowed). If there are N more inputs than outputs, there must be N more NANDs than splits.
Thus, a 31-NAND 8=&gt;4 module will neccessarily have 27 2-way splits.
Here are the split cardinalities for the above adder just in case larger splits are allowed:
18x wire (no split)
  4x output
  14x XOR 2nd stage
16x 2-way split
  8x input
  6x H2 input
  2x last bit XOR 1st stage
4x  3-way split
  4x XOR 1st stage
1x  4-way split
  1x 1st bit XOR 1st stage; if constants are alloweed; this is a three-way split