Dynamic programming
Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.
Running a computation backwards with little memory
The reverse sweep that gives a whole gradient for the price of a few evaluations needs the computation's intermediate states in reverse order, and storing them all can cost more memory than the machine has. Keep only a few and recompute the rest, and the cheapest schedule has an exact answer found by Andreas Griewank in 1992: with c stored states and no step run more than r times, the longest chain that can be reversed is the binomial coefficient C(c + r, c). Pascal's triangle is the table of what memory buys.
Nineteen fourth powers, and then sixteen
Edward Waring claimed in 1770 that every number is a sum of at most nineteen fourth powers. It is true, and it is needed: 79 takes nineteen, because its remainder on division by sixteen forces fifteen ones. But only seven numbers need nineteen, the last of them 559; the last to need eighteen is 1,248, and the last to need seventeen is 13,792. Counting every number to ten million shows the stragglers thinning out and the one obstruction that never goes away — the remainder modulo sixteen, which makes 31, 496, 7,936 and every 31·16ᵐ need sixteen for ever.
Named alongside it
The objects these essays reach for when they reach for this one.
Additive number theoryBinomial coefficientChain ruleCongruenceDerivativeFourth powerLower boundRecursionWarings problem