The denominations of U.S. coins make intuitive sense, but they can be unwieldy: It can take up to eight coins to assemble an amount up through 99¢. Indeed, producing 99¢ takes (1 × 50¢) + (1 × 25¢) + (2 × 10¢) + (4 × 1¢). What five denominations would minimize the number of coins ever needed to make change?

In The Math Chat Book, Frank Morgan reports that with coins of 1¢, 3¢, 11¢, 27¢, and 34¢, you never need more than 5 coins to make change. For example, now 99¢ = (2 × 34¢) + (1 × 27¢) + (1 × 3¢) + (1 × 1¢). Of the 1,129 possible solutions, this one requires the fewest coins on average (3.343).

Unfortunately, this system is a bit tricky too — to assemble some totals, it’s more efficient to use a few middle-size coins rather than starting with the largest value possible. For example, if you assemble 54¢ by starting with a 34¢ coin, it takes four additional coins to gather the remaining 20¢: (1 × 11¢) + (3 × 3¢). It would have been simpler to choose 2 × 27¢, but that’s not immediately evident.