Sylvester's Problem, a Second Look

James Joseph Sylvester was one the greatest British mathematicians of the 19th century. He was known for his absentmindedness and poor memory; on one occasion he even denied the truth of one of his own theorems. Still, he never forgot his origins. E.g., he was precluded from obtaining a Cambridge degree because it required to state his allegiance to the Church of England which he - being Jewish - refused to do.

In 1884 Sylvester submitted to the Educational Times the following problem:

A man possess a large quantity of stamps of only two denominations: 5-cent stamps and 17-cent stamps. What is the largest (finite) amount of cents which the man cannot make up with a combination of these stamps?

I've treated a more general problem

Let p and q be two mutually prime integers greater than 1. What is the largest number that could not be expressed as a linear combination ap + bq, with non-negative integers a and b?

elsewhere. The solution was based on the observation that the union of the arithmetic sequences

\(f_0 = \{0 + 0, 0 + q, 0 + 2q, 0 + 3q, \ldots\}\)
\(f_1 = \{p + 0, p + q, p + 2q, p + 3q, \ldots\}\)
\(f_2 = \{2p + 0, 2p + q, 2p + 2q, 2p + 3q, \ldots\}\)
\(f_3 = \{3p + 0, 3p + q, 3p + 2q, 3p + 3q, \ldots\}\)
\(\ldots\)
\(f_{q-1} = \{(q-1)p + 0, (q-1)p + q, (q-1)p + 2q, (q-1)p + 3q, \ldots\}.\)

covers the entire set of positive integers with some gaps at the beginning. (The sequence f_k consists of quantities that can be paid with k \(p\)-stamps and a number of \(q\)-stamps.) The sequences consist of the coefficients of the generating function

\(f(x) = \frac{1}{1-x^{q}}(1+x^p +x^{2p} +\ldots +x^{(q-1)p}) = \frac{1-x^{pq}}{(1-x^p)(1-x^q)}.\)

On the other hand, the generating function of all the nonnegative integers is simply

\(g(x) = 1+x+x^2+x^3+\ldots = \frac{1}{1-x}.\)

The difference of the two conceals the answer to Sylvester's problem: what quantity could not be represented by the stamps of two denominations.

\(g(x) - f(x) = \frac{1}{1-x} - \frac{1-x^{pq}}{(1-x^p)(1-x^q)} = \frac{(1-x^p)(1-x^q) - (1-x)(1-x^{pq})}{(1-x)(1-x^p)(1-x^q)}.\)

Since sequence \(f_k\) cover the entire set of positive integers with only some gaps at the beginning, this expression is finite, i.e., a polynomial. The degree of this polynomial is exactly the highest amount that could not be paid with \(p\)- and \(q\)-stamps; it is found from

\((pq + 1) - (p + q + 1) = pq - p - q,\)

which is the answer to Sylvester's problem.

The representation of the solution with generating function makes it easy to answer an additional question: what is the number of the amounts that could not be paid with \(p\)- and \(q\)-stamps? This number is equal to the number of nonzero coefficients in the polynomial. Since the polynomial is a finite part of the geometric series \(g(x) = 1+x+x^2+x^3+\ldots = \frac{1}{1-x},\) all of its nonzero coefficients equal 1. Their number could be found by substituting \(x=1\); however, since the polynomial is represented rather implicitly, the way to find its value at \(x=1\) is via L'Hôpital's Rule. It so happens that the rule needs to be applied three times. The third derivative of the numerator at \(x=1\) comes out to be \(-3pq(pq-p-q+1)\), and that of the denominator \(-6ab\). Thus the value of the polynomial is the quotient of the two:

\((pq -p -q+1)/2.\)

References

M. Erickson, Beautiful Mathematics, MAA, 2011

Generating Functions

41162630