Evaluation chains

The idea of building up computations like 1 + 1 + 1 + … from partial results has existed since Egyptian times. Since the late 1800s there have been efforts to find schemes that require the absolute minimum number of steps. The method based on IntegerDigits in the previous two notes can be improved (notably by power tree methods), but apparently about Log[t] steps are always needed. (Finding the optimal addition chain for given t may be NP-complete.)

One can also consider building up lists of non-identical elements, say by successively using Join. In general a length n list can require about n steps. But if the list contains a nested sequence, say generated using a substitution system, then about Log[n] steps should be sufficient. (Compare page 566.)