The largest amount two coins cannot pay

A country mints coins of only two values. Which amounts can be paid exactly? If the two values have a common factor, say 4 and 6, then only even amounts can be paid and the question has an unsatisfying answer. If they share no factor, then Euclid’s algorithm guarantees a combination $ax + by = 1$ with whole numbers $x$ and $y$, of which one is negative. So every amount can be made as long as debts are allowed. A shopkeeper does not give credit in quite that way, and so the real question is which amounts can be made with $x$ and $y$ both non-negative.

Small amounts often cannot. With coins of 5 and 7 there is no way to pay 1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18 or 23, and there is a way to pay everything else. So the gaps stop. How far do they run? The last gap is called the Frobenius number, after Georg Frobenius, who was said to bring it up in lectures. For two coins the answer is a one-line formula, a staple of mathematical recreations. For three coins it is a different world, with a precise theorem saying that no comparable formula exists. And for the structure the coins make, there is a count with an unexpected appearance of the golden ratio.

Reading the formula from a table #

The picture is the whole proof. Write out amounts in rows of length $a$, so that each column holds the amounts with one remainder modulo $a$. Adding a coin of value $a$ moves down one row in the same column. So once a column has a payable amount, everything below it in the column can be paid too. All that matters is the first arrival in each column.

First arrivals are multiples of $b$: 0, $b$, $2b$, …, $(a - 1)b$. Since $a$ and $b$ share no factor, these are all different modulo $a$, so each column is reached by exactly one of them. No smaller amount in that column can be paid, because paying it would need a smaller multiple of $b$ in the same column, and there isn’t one. So the last column to be reached is the one with first arrival $(a - 1)b$, and the gap just above it in that column is

$$(a - 1)b - a = ab - a - b.$$

For 5 and 7 that is 23. Counting the gaps is just as simple. Column $r$ has a first arrival at $kb$ for some $k$, and above that there are $\lfloor kb/a \rfloor$ gaps. Summing over all columns gives

$$\sum_{k=0}^{a-1}\left\lfloor \frac{kb}{a} \right\rfloor = \frac{(a - 1)(b - 1)}{2},$$

and that sum is the one that the rectangle counted twice evaluates in the proof of quadratic reciprocity. The count of lattice points under a diagonal is exact because the diagonal hits no lattice points when $a$ and $b$ have no common factor. For 5 and 7 there are 12 gaps. Both results were checked directly, for all coprime pairs of values below 40. James Sylvester posed the second as a problem in 1884, and it has been known since.

In how many ways #

Whether an amount can be paid is the first question, and how many ways it can be paid is the natural second. The answer turns the whole problem into a single expression. The number of ways $r(n)$ of paying $n$ with coins $a$ and $b$ is the coefficient of $x^n$ in

$$\frac{1}{(1 - x^a)(1 - x^b)},$$

which is the method of generating functions applied to the smallest possible case. Partial fractions give an exact formula, found by Tiberiu Popoviciu in 1953:

$$r(n) = \frac{n}{ab} - \left\{\frac{b^{-1}n}{a}\right\} - \left\{\frac{a^{-1}n}{b}\right\} + 1,$$

where the braces mean the fractional part and $b^{-1}$ is the inverse of $b$ modulo $a$. For coins of 5 and 7 this agrees with direct counting at every amount below 3,000: nought ways for 23, one for 24 and one for 34, two for 35, three for 70, and 29 for 1,000. So the count is the plain average $n/ab$ plus a correction that is periodic with period $ab$ and never larger than one, and an amount is a gap exactly when those corrections cancel the average completely. The mirror symmetry falls out too: the formula satisfies $r(n + ab) = r(n) + 1$, and $r(F - n) = 1 - r(n)$ for $n$ between 0 and $F$. With three coins the same expression has a double pole and a more complicated periodic part, with terms that are generalised Dedekind sums; the count is a quadratic polynomial in $n$ with periodic coefficients, and that is the source of the lack of a neat rule for the last place where it falls to nought.

A symmetry #

There is a strange feature of the board: exactly half of the numbers from 0 to $F$ are gaps. That is what $(a-1)(b-1)/2$ out of $F + 1 = (a - 1)(b - 1)$ says. It reflects something much stronger.

For two coins, exactly one of $n$ and $F - n$ can be paid. The figure shows the amounts from 0 to $F$ as a bar, and reversing the bar swaps its colours, for all pairs shown and every one of those numbers. The proof takes a line. Any integer $n$ can be written uniquely as $ax + by$ with $0 \le x < b$, and it can be paid exactly when $y \ge 0$. Then $F - n = ab - a - b - ax - by = a(b - 1 - x) + b(-1 - y)$, and the new coefficient of $b$ is negative exactly when the old one was not.

Semigroups with this mirror symmetry are called symmetric, and they are the first indication that two coins are special. In the theory of singularities of curves, a set of amounts like this describes the possible orders of vanishing of functions at a point of a plane curve with a cusp, of the form $x^a = y^b$. The symmetry is then a form of duality for that curve. It is called the Gorenstein property, and the number of gaps is the curve’s genus. A pair of coins has a good geometric meaning, and the numbers are the exponents in a local expansion. With three coins the symmetric ones can be listed by a known criterion, but typical choices of three coins do not have the symmetry. So there is no exact half.

Three coins, and a proof that no formula exists #

A set such as 6, 9 and 20 has a last gap of 43, a number often quoted because of the boxes of fried chicken in those sizes. There is no way to read it off from the three values in the style of $ab - a - b$. F. Curtis made that into a theorem in 1990: no finite set of polynomials in three variables can give the Frobenius number for all triples. There is therefore no closed form of the expected kind. The number does have algorithms, however, and those show what kind of object it really is.

The method of rows still applies, with the smallest coin setting the number of columns. Now a column has its first arrival reached by a combination of the other two coins, and the question is a shortest path in a graph. Nodes are remainders modulo $a$. An edge for coin $c$ goes from $r$ to $r + c$, with length $c$. The first arrival in each column is the shortest-path distance from nought. For 6, 9 and 20, the distances are 0, 49, 20, 9, 40, 29; the last column is at 49, and the last gap is $49 - 6 = 43$. This is the formula of Alfred Brauer and James Shockley. The number of gaps follows too, by summing $\lfloor d_r/a \rfloor$, giving 22. So the fact that there is no formula is entirely consistent with its being fast to compute: for fixed smallest coin it is a small shortest-path problem. Jorge Ramírez Alfonsín showed in 1996 that as the number of coins grows, finding the Frobenius number is NP-hard, so it stops being easy, but that hardness is about the number of coins. Each individual set of a few coins is a very modest computation, and it can be done for coins of a hundred digits with three coins.

The method gives a general formula for two coins in a single step, since a single run through the multiples of $b$ visits every column. With three the graph has two kinds of edges and its shape depends on the continued fraction of a ratio of the coins, and this is what gives Harold Greenberg’s and Ø. Rødseth’s algorithms a form reminiscent of Euclid’s algorithm on continued fractions. So three coins still do have an algorithm in the spirit of Euclid, only no formula.

What a typical triple does #

There is no formula, but there is a typical size. Vladimir Arnold suggested in 1999 that the Frobenius number of random coins of a given size should behave very regularly, and this has now been confirmed in various forms. It should be about $\sqrt{abc}$ times some random factor.

Among 2,101 random triples of coins from 40 to 400, the quantity $F/(2\sqrt{abc})$ has median 0.886 and goes as high as 6.39 in its long tail. For comparison, two coins have $F \approx ab$, and the corresponding lower bound of Rødseth for three is about $\sqrt{3abc}$ for any triple. The distribution is the interesting object. Jens Marklof showed in 2010, by treating the coins as defining a lattice, that the ratio has a limit distribution as the coins grow. Its tail comes from triples that are close to having a shared factor, for which the last gap is pushed far out. In that respect a triple is much like a random lattice, and the Frobenius number is a measure of the lattice’s largest empty region, a covering radius. Iskander Aliev, Martin Henk and Lenny Fukshansky have developed this into bounds for any number of coins. So the question moves into the same geometry that the lattice of points on a circle lives in.

Boxes of chicken and shared factors #

A few examples show how sensitive this is, and the same arithmetic of sums turned up, in a very different setting, in which sizes of choice follow from pairs, where the coins are the primes above a given bound. With the original boxes of 6, 9 and 20, the last amount that cannot be bought is 43. Adding a box of 4 brings the last gap down to 11, a large change from one more coin, because the new coin is smaller and it has an odd interaction with 9. With only 6 and 9, there is no last gap, since every amount has to be a multiple of 3. The set 6, 10, 15 has no factor common to all three, although every pair has one, and its last gap is 29. There is a nice construction here: a product of two primes for each pair of coins will always behave that way. And for such sets there is a formula: with coins of $pq$, $pr$ and $qr$ for pairwise coprime numbers, the last gap is $2pqr - pq - pr - qr$, which gives $60 - 31 = 29$ here.

The practical versions of this are older than the name. Postage stamps have been a standard form of the question. And there is a classic counterpart in the divisors of a number that make every amount, where instead of asking which amounts one set misses, one asks which numbers have divisors that miss nothing. In both cases, a small additive question about a fixed set of numbers turns out to depend on its arithmetic in a delicate way.

All the sets coins can make #

The set of amounts that a collection of coins can pay is closed under addition, contains 0, and misses only finitely many numbers. Such a thing is called a numerical semigroup, and every numerical semigroup comes from a finite set of coins. So here is a natural question with no coins in it. How many numerical semigroups have exactly $g$ gaps?

The count can be organised as a tree. From any semigroup, remove a generator larger than the last gap, to get a semigroup with one more gap, and every semigroup arises in exactly one way. A depth-first search then computes the counts: 1, 1, 2, 4, 7, 12, 23, 39, 67, 118, 204, 343, 592, 1,001, …, and 770,832 at 26 gaps. In 2008 Maria Bras-Amorós looked at the ratio of consecutive counts from such a table and conjectured that it tends to the golden ratio, with the counts also behaving like Fibonacci numbers in that each is at least as large as the sum of the previous two. At 26 gaps the ratio is 1.650, and it is falling, very slowly, towards $\varphi = 1.618$ from above. The appearance of $\varphi$ in a question with no obvious recursion was a complete surprise.

Alex Zhai proved the limit in 2013. The reason is that nearly all semigroups with $g$ gaps have a Frobenius number less than three times their smallest generator, and this class has a structure that can be counted by compositions and that produces a Fibonacci recursion. It is a strange fact, then, that nobody can prove the simplest property: that the counts never decrease. Each count in the table is greater than the last, and Zhai’s theorem implies that this holds from some point on, but no proof has been found that it holds at every $g$. The table is known to go up into the seventies by exhaustive search, by Jean Fromentin and Florent Hivert, and nothing has gone wrong. It is hard to imagine a more elementary open question.

What was exact and what was not #

The two-coin formulas were tested exactly for all pairs below 40, and they come with a short proof. The symmetric bars are exact for the five pairs shown. The computations of the Frobenius number with three coins use the shortest-path method and are exact; the claim for 6, 9 and 20 was tested separately by a table of payable amounts up to 100. The histogram of random triples is a sample of about two thousand with a modest range, it is a picture rather than an estimate, and the convergence results cited for it are from the literature. Curtis’s theorem and the NP-hardness are quoted. So are Marklof’s result and the use of covering radii.

The semigroup counts through 26 gaps are exact and agree with the published table. The golden-ratio limit is Zhai’s theorem. The ratio at the end of the table is not close enough to $\varphi$ to establish anything by itself. The formula for coins of the form $pq$, $pr$, $qr$ has been checked here only on the one example drawn; the general statement is standard but was not derived.

Still open: never decreasing, and Wilf’s inequality #

Does the number of numerical semigroups with $g$ gaps never decrease? That is, is $n_{g+1} \ge n_g$ for every $g$? It has been verified well past 60, and it is implied for all large $g$ by Zhai’s theorem. Nothing has been proved at each $g$.

The second famous open problem is Herbert Wilf’s conjecture of 1978. Let a semigroup have Frobenius number $F$, smallest non-zero element $m$, $e$ minimal generators, and let $L$ be the number of elements below $F$. Wilf conjectured that $e \cdot L \ge F + 1$: a semigroup with few generators must have a lot of elements below its last gap. The conjecture has been checked for all semigroups up to genus 60 by Fromentin, and it is proved for many special families, by Shalom Eliahou among others. It remains open in general. It is a statement about how much a few generators can force, in the same style as the bound $ab - a - b$, and it has the same flavour as the fifteen values that decide a quadratic form, where a finite check controls all the rest. One might expect it to have a simple proof. None has been found in almost fifty years.

A board and its first arrivals #

For two coins, each remainder class is reached first by a multiple of the larger coin, so the last gap is $ab - a - b$, the count of gaps is $(a - 1)(b - 1)/2$, and exactly one of $n$ and $F - n$ can be paid. For three coins, the first arrivals become a shortest-path problem, and a theorem rules out any formula. For the sets that coins can make, the count of those with $g$ gaps grows like the golden ratio to the power $g$.

These are three levels of the same arrangement, and they share the same device. It is the rows of length $a$, from which the proofs can be read. That something as modest as paying for a thing in coins should reach from a one-line formula to a theorem forbidding formulas, and on to a question that nobody can answer about a table of whole numbers, is a measure of how much arithmetic is contained in the phrase “with non-negative coefficients”.