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

$\displaystyle 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

$\displaystyle 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.

$\displaystyle 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 $\displaystyle 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

72091534