Four Shillings

A till hands you the largest coin that fits, then the largest that fits in what is left, and so on until it is done. That rule is not always the fewest coins. Whether it is depends entirely on which coins a country decided to mint: British money got it right until 1836, got it wrong for the next hundred and thirty-three years, and repaired itself thirteen months before it was abolished. One currency circulating today still gets it wrong, on one amount in ten. Operate a till below in any currency you like and hunt for the amount where it loses.

What the rule is, and when it is wrong

Call a set of denominations canonical when greedy is optimal for every amount, without exception. Most of the world's coinage is canonical, which is why nobody notices the question exists. The classic toy failure is {1, 3, 4}: to pay 6 the greedy rule takes the 4, then can only add two 1s, three coins, where two 3s would have done it in two.

The property is decidable. Kozen and Zaks proved in 1994 that if a system fails at all, the smallest amount it fails on lies strictly between c₃ + 1 and c_m-1 + c_m, the sum of the two largest coins. So a finite scan settles it forever, and the hunt button above is doing exactly that scan in your browser: it is not sampling, it is deciding.

Britain broke it, twice, and fixed it twice

Sterling before decimalisation is the standard example of a currency where greedy is wrong, and it is not folklore: David Pearson put it in print in the paper that gave the first polynomial-time test for the property.

“48 pence would be represented as 30+12+6 by the greedy algorithm, while the minimal representation is 24+24 (two florins).”

Four shillings. Half a crown, a shilling and a sixpence, when two florins would have done. But the pre-decimal system was not one system: it was a sequence of them, and the property switches on and off as coins arrive and leave. Every date below comes from the instrument that made it, a Royal Proclamation in The Gazette or an Act, and the verdict beside it is recomputed in your browser from the coins of that year.

Two repairs are worth naming. The double florin of 1887, a four-shilling piece that lasted three years and was widely disliked, plugged the hole exactly: four shillings became one coin, and the failure at 48 pence had nowhere to go. And the half-crown, called in by proclamation with effect from 1 January 1970, was the coin whose absence made the whole system canonical again, thirteen months before it was replaced wholesale. Sterling got the property right just in time to lose it.

One honest wrinkle, because it moves the verdict: the 1887 repair holds for the coins people actually carried. Count the crown, legal tender but by then a commemorative piece rather than circulating money, and the system fails again at 78 pence (crown plus shilling plus sixpence, where a double florin plus a half-crown is two coins). Whether Britain's money was greedy-optimal in 1888 depends on whether you count a coin nobody had in their pocket. The table above takes the circulating set, and the choice is stated rather than hidden.

“Almost all real currency systems”

A 2023 paper in Theoretical Computer Science says, in passing, that “for almost all real currency systems, the greedy algorithm outputs an optimal solution.” It gives no citation and no survey, and as far as an adversarial search of the literature could establish, nobody had counted. Kozen and Zaks assert it of American and Israeli coins in 1994; other papers assert it of the dollar and the euro. Those are four currencies. The word doing the work is almost, and nobody had checked whether it was needed.

It is needed. Here is the count, over every currency whose issuing authority publishes a circulating coin series on a page that could be fetched and quoted. One of them fails.

Every other currency here is canonical, which is the more interesting half of the result: it means the assertion in the literature is true, and true for a reason worth seeing. Almost every coin series on Earth is built from 1, 2 and 5 times a power of ten, and every such series is canonical. The exceptions that do exist mostly sit in the other direction: two currencies below cannot pay every amount in coin at all, because their smallest coin is larger than the grid their values sit on.

The verdict in each row is recomputed in your browser from the denominations, not read from a stored answer. Sort of check you can do yourself: pick any row in the till above and press the hunt button.

Eight currencies are missing and the reason is recorded for each: three issuers (New Zealand's Reserve Bank, the State Bank of Pakistan, Paraguay's central bank) refuse automated requests outright, four publish no list of what circulates, and Bulgaria is not a separate case any more, having adopted the euro on 1 January 2026. This is a census of what could be sourced, not of the world, and the difference is stated rather than smoothed over.

How rare is it to be canonical?

Rare, and it gets rarer fast. Below is an exact count: of all the coin systems whose largest denomination is exactly n (every subset of the values in between, with 1 and n always present, so 2^n-2 systems in all), how many are canonical.

The counts to n = 25 agree exactly with those derived from OEIS A390211, which enumerates the canonical systems themselves; the rows beyond that go past the end of its table. The sequence of counts is not itself in the encyclopedia, but it is a two-line derivation from an entry that is, so it is an extension and not a discovery.

The best coinage is one your till cannot use

If you were designing a currency from scratch and wanted the fewest coins per transaction, you would not choose the American set. Averaged over every amount from 0 to 99 cents, {1, 5, 10, 25} costs 4.70 coins. {1, 5, 18, 25} costs 3.89, which is where the proposal for an 18-cent piece comes from. But that set is not canonical: a greedy till pays out 4.63 on it, and only an algorithm that plans ahead gets 3.89. The best system you can actually spend, at four denominations, is {1, 3, 11, 37} at 4.14.

Every figure in that table is Shallit's, from 2003, and reproduced here rather than discovered; the verifier checks all twenty of his published averages exactly. What is added is the last column at six denominations, where for the first time no greedy-optimal set is canonical at all and the best usable system costs a hundredth of a coin more.