Mathematics
Frobenius Coin Problem and the Largest Unpayable Amount
Quick fact
For two coprime denominations a and b, the largest nonrepresentable amount is ab – a – b. For the classic chicken nuggets problem with 6, 9, and 20, the largest non-orderable number is 43.
Why this is interesting
You have two coins, say 3 and 5 cents. What is the largest amount you cannot make? Surprisingly, there is a simple formula—and for some sets of coins, the answer can be surprisingly large.
Read the full explanation
Understanding Frobenius Coin Problem and the Largest Unpayable Amount
Imagine you have an unlimited supply of two coin denominations, say 4 and 7 cents. You can make 4, 7, 8, 11, 12, 14, 15, 16, and so on. But you cannot make 1, 2, 3, 5, 6, 9, 10, 13, or 17 cents. The largest amount you cannot make is 17. As you go higher, eventually every amount becomes representable. Why? Because once you have a run of consecutive representable numbers, you can extend it by adding the smaller coin. The key condition is that the two denominations must be coprime (have no common divisor greater than 1). If they share a common divisor, then you can only make multiples of that divisor, so infinitely many amounts are impossible. With coprime numbers, you can reach every sufficiently large integer. The Frobenius coin problem asks for the boundary: what is the largest integer that is NOT representable?
A deeper explanation
The problem is to find the largest positive integer that cannot be expressed as a nonnegative integer combination of given coin denominations, when the greatest common divisor of all denominations is 1. For two denominations a and b, the answer is given by the formula ab – a – b. This formula emerges from the fact that for any integer n, exactly one of n and ab – a – b – n is representable. This symmetry ensures that the largest nonrepresentable number is exactly ab – a – b. For more than two denominations, no simple closed-form formula is known; the problem becomes computationally hard. The Frobenius number finds applications in combinatorics, computer science (e.g., allocating resources), and even in understanding the structure of numerical semigroups—sets of nonnegative integers closed under addition that contain all sufficiently large integers. Understanding this problem reveals the delicate line between representable and nonrepresentable quantities, driven purely by the arithmetic properties of the denominations.