Cellular automaton [Nand] formulas

For 1 step, the elementary cellular automaton rules are exactly the 256 n=3 Boolean functions. For 2 steps, they represent a small subset of the 2^{32} n=5 functions. They require an average of about 11.6 Nand operations, and a maximum of 27 (achieved by rules 107 and 121).

For rule 254 the result after t steps (which is always asymmetric, even though the rule is symmetric) is

Nest[{{#, #[[2]] + 1}, #[[2]] + 1} &, {{1, 1}, {2, 2}}, t - 2]

If explicit copy operations were allowed, then the number of Nand operations after t steps could not increase faster than t^{2} for any rule. But without copy (fanout) operations no corresponding result is immediately clear.