Welcome to the Feature Column

---

The Frobenius Problem: How I bought Chicken McNuggets with exact change

Though the problem seems like one from discrete mathematics, we will see an unexpected interplay between the continuous and discrete worlds as we use somewhat elementary techniques from calculus to arrive at a solution....

Mail to a friend

Print this article

Introduction

Now that August is here and you're planning that overseas getaway, it's time to think about other systems of currency.

For instance, suppose you are in a country whose currency comes only in denominations of 11 and 21 quatloos. Sure, it's a strange system, but the country is known for its great food. So when your waiter brings you a check for 100 quatloos, will you be able to pay with exact change?

Stated mathematically, you'd like to find a solution to the equation \[ 11x + 21 y= 100 \]

where $x$ and $y$ are nonnegative integers.

More generally, suppose we are in a country whose currency consists of denominations of $a_1, a_2, \ldots, a_d$ and ask if we can pay a bill of $n$ without needing change. In other words, can we find nonnegative integers $x_1,x_2,\ldots, x_d$ such that \[a_1x_1 + a_2x_2 + \ldots + a_dx_d = n?\]

This problem arises in other ways as well. For instance, postage stamps come in a limited number of denominations so we need to solve this equation to mail a package with exact postage. American football allows scores of 2, 3, 6, 7, and 8 points; if we see that a team has scored 31 points, we feel fairly confident they have scored four touchdowns and a field goal. Until recently, McDonald's Chicken McNuggets came in boxes with 6, 9, or 20 McNuggets presenting us with the Chicken McNugget problem.

As we'll see, with a mild assumption on the denominations, there are only finitely many values of $n$ for which there are no solutions. Determining the largest such $n$ is sometimes called the Frobenius problem, named after the 19^th century mathematician Ferdinand Georg Frobenius, who is said to have originally discussed this problem.

This article presents a solution to the Frobenius problem in the simplest case that there are two denominations of currency. Though the problem seems like one from discrete mathematics, we will see an unexpected interplay between the continuous and discrete worlds as we use somewhat elementary techniques from calculus to arrive at a solution.

The case when $d=2$

We will begin with the simplest case in which there are only two denominations of currency, which we will denote by $a$ and $b$. Our question is then: given a nonnegative integer $n$, can we find nonnegative integers $x$ and $y$ such that \[ax + by = n.\]

If there is a solution, we say that $n$ is representable.

When $a$ and $b$ are not relatively prime, we may easily find numbers that are not representable. For instance, if $a$ and $b$ are even, then any odd number is not representable. To prevent this kind of situation, we will therefore require that $a$ and $b$ are relatively prime. Of course, the general case can be reduced to this one by dividing out the greatest common divisor.

In the case that $a$ and $b$ are relatively prime, the Euclidean algorithm implies that there are integers $p$ and $q$ such that $ap + bq = 1$. However, it is not possible for both $p$ and $q$ to be nonnegative. For instance, if $a=5$ and $b = 8$, we have $(-3)a + 2b = 1$. In other words, if we need to pay a 1-unit check, we could pay with two 8-unit bills and receive three 5-unit bills as change. However, we could not pay with exact change.

This problem has a geometric interpretation that is useful to keep in mind. The equation $ax + by = n$ describes a line in the plane; shown below are two such lines when $a=4$ and $b=7$.

 

The integer $n$ is representable precisely when a point on the integer lattice lies on the line $ax+by=n$. In the case when $a=4$ and $b=7$, we see that $n=10$ is not representable, while $n=19$ is.

The following figure considers all possible $n$. Lines corresponding to representable integers $n$ are gray, and those corresponding to nonrepresentable integers are red.

 

This figure validates an intuitive notion that says larger values of $n$ are more likely to be representable than smaller values. In fact, there are only finitely many $n$ that are not representable. The largest such $n$ is called the Frobenius number and will be denoted $g(a,b)$; in the case that $a=4$ and $b=7$, the figure shows that the Frobenius number $g(4,7)=17$.

 

We will develop an expression for the Frobenius number in the case that $d=2$.

Comments?

The restricted partition function and its generating function

In an effort to find which $n$ are representable, we will take two seemingly ambitious steps.

First, let's not just ask if a number $n$ is representable; let's ask how many solutions there are to the equation $ax+by=n$. We define the restricted partition function $p_{\{a,b\}}(n)$ to be the number of nonnegative integral solutions $(x,y)$. The integer $n$ is representable precisely when $p_{\{a,b\}}(n) > 0$.

Second, rather than focusing on $p_{\{a,b\}}(n)$ for a single value of $n$, let's consider them all at once. We will do so by creating the restricted partition function's generating function: \[ \begin{eqnarray*} f(z) &=& \sum_{n=0}^\infty p_{\{a,b\}}(n) z^n \\ & = & p_{\{a,b\}}(0)+p_{\{a,b\}}(1) z+p_{\{a,b\}}(2) z^2 + \ldots + p_{\{a,b\}}(n) z^n + \ldots \\ \end{eqnarray*} \]

At this time, let's not worry about the values of $z$ for which this infinite power series converges. It will, however, be useful to remember the geometric series: \[ \frac1{1-z^c} = 1 + z^c + z^{2c} + \ldots + z^{ck} +\ldots= \sum_{k\geq0}z^{ck}, \]

which holds when $|z| < 1$.

Now remember that $p_{\{a,b\}}(n)$ is the number of nonnegative integral solutions to the equation $ax + by = n$. In other words, $p_{\{a,b\}}(n)$ is the number of nonnegative pairs $(j, k)$ such that $aj + bk = n$. With this observation, we may rewrite the generating function as \[ \begin{eqnarray*} f(z) & = & \sum_{j\geq 0}\sum_{k\geq0} z^{aj+bk} \\ & = & \sum_{j\geq 0}z^{aj} \sum_{k\geq0} z^{bk} \\ & = & \frac{1}{1-z^a}\frac{1}{1-z^b}. \end{eqnarray*} \]

In other words, we have \[ \frac{1}{(1-z^a)(1-z^b)} = p_{\{a,b\}}(0)+p_{\{a,b\}}(1) z+p_{\{a,b\}}(2) z^2 + \ldots + p_{\{a,b\}}(n) z^n + \ldots. \]

By the way, this shows that the infinite series defining $f(z)$ converges when $|z|<1$ so that we may view $f(z)$ as an analytic function around $z=0$.

It looks like we're making progress. Let's now go back and focus on a specific value of $n$, which we will isolate by dividing by $z^n$: \[ \begin{eqnarray*} \frac{1}{(1-z^a)(1-z^b)z^n} &=& \frac{p_{\{a,b\}}(0)}{z^n}+ \frac{p_{\{a,b\}}(1)}{z^{n-1}}+ \ldots + \frac{p_{\{a,b\}}(n-1)}{z}+ \\ & & p_{\{a,b\}}(n) + p_{\{a,b\}}(n+1)z + \ldots. \end{eqnarray*} \]

This operation exchanges our infinite power series for a Laurent series, which includes negative powers of $z$. The term we seek, $p_{\{a,b\}}(n)$, is the constant term of this series.

Comments?

A partial fraction expansion

From this point, our strategy is to find a partial fraction expansion of the left hand side of the expression above. To this end, remember that the roots are $1-z^a$ are given by the $a^{th}$ roots of unity, $\zeta_a^j=e^{2\pi i j/a}$ for $j=0,1,2,\ldots,a-1$. There is, of course, one special root: when $j=0$, $\zeta_a^0 = 1$. We therefore arrive at the factorization \[ 1-z^a=-(z^a-1) = -\prod_{j=0}^{a-1}(z-\zeta_a^j) =-(z-1)\prod_{j=1}^{a-1}(z-\zeta_a^j), \]

which, assuming $a$ and $b$ are relatively prime, leads to the partial fraction expansion \[ \begin{eqnarray*} \frac1{(1-z^a)(1-z^b)z^n} &=& \frac1{z^n(z-1)^2\prod_{j=1}^{a-1}(z-\zeta_a^j)\prod_{k=1}^{b-1} (z-\zeta_b^k)} \\ & = & \frac{A_1}z + \frac{A_2}{z^2} + \ldots + \frac{A_n}{z^n} \\ & & + \frac{B_1}{z-1}+\frac{B_2}{(z-1)^2} \\ & & + \sum_{j=1}^{a-1} \frac{C_j}{z-\zeta_a^j} + \sum_{k=1}^{b-1} \frac{D_k}{z-\zeta_b^k}. \end{eqnarray*} \]

Let's compare this expression to the one we previously found: \[ \begin{eqnarray*} \frac{1}{(1-z^a)(1-z^b)z^n} &=& \frac{p_{\{a,b\}}(0)}{z^n}+ \frac{p_{\{a,b\}}(1)}{z^{n-1}}+ \ldots + \frac{p_{\{a,b\}}(n-1)}{z}+ \\ & & p_{\{a,b\}}(n) + p_{\{a,b\}}(n+1)z + \ldots. \end{eqnarray*} \]

The restricted partition function $p_{\{a,b\}}(n)$ appears as the constant term of this Laurent series. We may neglect the negative powers of $z$ to see that: \[ \begin{eqnarray*} p_{\{a,b\}}(n) & = & \left.\left(\frac{B_1}{z-1}+\frac{B_2}{(z-1)^2} + \sum_{j=1}^{a-1} \frac{C_j}{z-\zeta_a^j} + \sum_{k=1}^{b-1} \frac{D_k}{z-\zeta_b^k}\right)\right|_{z=0} \\ & = & -B_1 + B_2 - \sum_{j=1}^{a-1} \frac{C_j}{\zeta_a^j} - \sum_{k=1}^{b-1} \frac{D_k}{\zeta_b^k} \end{eqnarray*} \]

Therefore, to compute the restricted partition function $p_{\{a,b\}}(n)$, we only need to evaluate the coefficients $B_1$, $B_2$, $C_j$ and $D_k$ in the partial fraction expansion: \[ \begin{eqnarray*} \frac1{(1-z^a)(1-z^b)z^n} &=& \frac1{z^n(z-1)^2\prod_{j=1}^{a-1}(z-\zeta_a^j)\prod_{k=1}^{b-1} (z-\zeta_b^k)} \\ & = & \frac{A_1}z + \frac{A_2}{z^2} + \ldots + \frac{A_n}{z^n} \\ & & + \frac{B_1}{z-1}+\frac{B_2}{(z-1)^2} \\ & & + \sum_{j=1}^{a-1} \frac{C_j}{z-\zeta_a^j} + \sum_{k=1}^{b-1} \frac{D_k}{z-\zeta_b^k}, \end{eqnarray*} \]

Comments?

Computing the restricted partition function

We will begin with $B_2$. Multiply by $(z-1)^2$ and let $z\to 1$ to obtain: \[ B_2 = \lim_{z\to1} \frac{(z-1)^2}{(1-z^a)(1-z^b)z^n}. \]

Applying l'Hôpital's rule twice shows that $B_2 = \frac1{ab}$.

We may find $B_1$ in a similar way. Subtract $B_2/(z-1)^2$ from both sides of the equation, multiply by $z-1$ and let $z\to 1$. This gives: \[ B_1 = \lim_{z\to 1}\left(\frac{z-1}{(1-z^a)(1-z^b)z^n} - \frac{\frac1{ab}}{(z-1)^2}\right). \]

Applying l'Hôpital's rule three times shows that \[ B_1 = \frac1{ab} - \frac1{2a} - \frac1{2b} -\frac n{ab}. \]

Finally, the coefficients $C_j$ may be computed by multiplying by $z-\zeta_a^j$ and letting $z\to\zeta_a^j$. A dose of l'Hôpital's rule shows that \[ \begin{eqnarray*} C_j&=&\lim_{z\to\zeta_a^j}\frac{z-\zeta_a^j}{(1-z^a)(1-z^b)z^n} \\ &=&-\frac1{a\zeta_a^{j(a-1)}(1-\zeta_a^{jb})\zeta_a^{jn}} \\ &=&-\frac1{a\zeta_a^{-j}(1-\zeta_a^{jb})\zeta_a^{jn}} \\ &=&-\frac1{a(1-\zeta_a^{jb})\zeta_a^{j(n-1)}}. \end{eqnarray*} \]

Similarly, \[ D_k=-\frac1{b(1-\zeta_b^{ja})\zeta_b^{k(n-1)}}. \]

Finally, if we remember that \[ p_{\{a,b\}}(n) = -B_1 + B_2 - \sum_{j=1}^{a-1} \frac{C_j}{\zeta_a^j} - \sum_{k=1}^{b-1} \frac{D_k}{\zeta_b^k}, \]

then we arrive at \[ p_{\{a,b\}}(n) = \frac1{2a} + \frac1{2b} + \frac n{ab} + \frac1a \sum_{j=1}^{a-1}\frac1{(1-\zeta_a^{jb})\zeta_a^{jn}} + \frac1b \sum_{k=1}^{b-1}\frac1{(1-\zeta_b^{ja})\zeta_b^{kn}}. \]

Comments?

Computing the Fourier-Dedekind sums

The terms of the form \[ \frac1a \sum_{j=1}^{a-1}\frac1{(1-\zeta_a^{jb})\zeta_a^{jn}} \]

appearing in our expression for $p_{\{a,b\}}(n)$ are examples of Fourier-Dedekind sums. Though it is useful to note that these sums may be evaluated as Fourier transforms, we will evaluate them using a simpler observation.

Remembering that \[ p_{\{a,b\}}(n) = \frac1{2a} + \frac1{2b} + \frac n{ab} + \frac1a \sum_{j=1}^{a-1}\frac1{(1-\zeta_a^{jb})\zeta_a^{jn}} + \frac1b \sum_{k=1}^{b-1}\frac1{(1-\zeta_b^{ja})\zeta_b^{kn}}, \]

we consider the case where $b=1$ to find \[ p_{\{a,1\}}(n) = \frac1{2a}+\frac12 + \frac n{a} + \frac1a \sum_{j=1}^{a-1}\frac1{(1-\zeta_a^{j})\zeta_a^{jn}}. \]

However, the restricted partition function $p_{\{a,1\}}(n)$ is easily understood in this case; it is the number of nonnegative solutions $(x,y)$ to $ax + y = n$. There is one solution for each $x$ such that $0\leq x \leq \frac na$. In other words, $p_{\{a,1\}}(n)$ equals the number of integers in the closed interval $[0,\frac na]$.

If we use $\lfloor z\rfloor$ to denote the greatest integer less than or equal to $z$, then we have \[p_{\{a,1\}} = \left\lfloor \frac na\right\rfloor + 1,\]

and so \[ p_{\{a,1\}}(n) = \left\lfloor \frac na\right\rfloor + 1 = \frac1{2a}+\frac12 + \frac n{a} + \frac1a \sum_{j=1}^{a-1}\frac1{(1-\zeta_a^{j})\zeta_a^{jn}}. \]

This implies that \[ \begin{eqnarray*} \frac1a \sum_{j=1}^{a-1}\frac1{(1-\zeta_a^{j})\zeta_a^{jn}} & = & \left\lfloor \frac na\right\rfloor +\frac12-\frac1{2a} - \frac n{a} \\ & = & -\left\{\frac na\right\} + \frac 12 - \frac1{2a}, \end{eqnarray*} \]

where $\left\{z\right\} = z - \lfloor z \rfloor$ is the fractional part of $z$.

We may apply this to evaluate the Fourier-Dedekind sum appearing in our general expression for $p_{\{a,b\}}(n)$. Since $a$ and $b$ are relatively prime, we may find $b^{-1}$ where $b\cdot b^{-1} \equiv 1 \bmod{a}$ and sum over $j'=jb$ to see that \[ \frac1a \sum_{j=1}^{a-1}\frac1{(1-\zeta_a^{jb})\zeta_a^{jn}} = \frac1a \sum_{j'=1}^{a-1}\frac1{(1-\zeta_a^{j'})\zeta_a^{j'b^{-1}n}} = = -\left\{\frac {b^{-1}n}a\right\} + \frac 12 - \frac1{2a}. \]

After all this, we may rewrite the Fourier-Dedekind sums in our expression for $p_{\{a,b\}}(n)$ to arrive at the following remarkable formula known as

Popoviciu's theorem: If $a$ and $b$ are relatively prime, then \[ p_{\{a,b\}}(n) = \frac n{ab} - \left\{\frac{b^{-1}n}{a}\right\} - \left\{\frac{a^{-1}n}{b}\right\} + 1, \] where $a\cdot a^{-1} \equiv 1\bmod{b}$ and $b\cdot b^{-1} \equiv 1\bmod{a}$.

Let's look at an example when $a=4$, $b=7$ and $n=107$. In this case, we have $2a + (-1)b = 1$, which means we may take $a^{-1} = 2$ and $b^{-1} = -1$. Therefore, \[ \begin{eqnarray*} p_{\{4,7\}}(107) &=& \frac{107}{4\cdot7}-\left\{\frac{-107}{4}\right\}- \left\{\frac{2\cdot107}{7}\right\} + 1 \\ &=&\frac{107}{28}-\frac14-\frac47+1 \\ &=&4+\frac{23}{28}-\frac14-\frac47 \\ &=&4. \end{eqnarray*} \]

There are then four ways of representing 107 as a linear combination of 4 and 7: \[ 107=4\cdot4+13\cdot7=11\cdot4+9\cdot7=18\cdot4+5\cdot7=25\cdot4+1\cdot7. \]

Returning to the original question about whether I could pay my 100 quatloo check with exact change, we see that with $a = 11, b= 21$ and $n = 100$, there are zero ways of representing 100 as a linear combination of 11 and 21. Looks like it’s time to prepare for the inevitable—and awkward—query from the waiter: “Do you need change?”

Comments?

The Frobenius number

We noted earlier that it seems clear that there are only finitely many integers $n$ that are not representable and we called the largest nonrepresentable integer the Frobenius number. Popoviciu's theorem tells us that $p_{\{a,b\}}(n)$ grows in a roughly linear fashion, which, as we'll now see, explains why there are only finitely many nonrepresentable integers.

First, observe: if $p$ is an integer, then $\left\{\frac pa\right\}$ belongs to the set $\{0, \frac 1a,\frac 2a, \ldots, \frac{a-1}{a}\}$, which implies that $\left\{\frac pa\right\} \leq\frac{a-1}a.$

Let's now consider \[ \begin{eqnarray*} p_{\{a,b\}}(n) &=&\frac n{ab} - \left\{\frac{b^{-1}n}{a}\right\} - \left\{\frac{a^{-1}n}{b}\right\} + 1 \\ &\geq&\frac{n}{ab}-\frac{a-1}{a}-\frac{b-1}{b}+1 \\ &\geq&\frac{n-(a-1)b-(b-1)a+ab}{ab} \\ &\geq&\frac{n-[ab-a-b]}{ab} \end{eqnarray*} \]

This shows that if $n> ab-a-b$, then $p_{\{a,b\}}(n)>0$ and so $n$ is representable. In other words, we have found an upper bound for the nonrepresentable integers, and the Frobenius number will be less than or equal to $ab-a-b$.

We can do still more. If you play around with our expression for $p_{\{a,b\}}(n)$, you may begin to notice a symmetry. To see this, first note that $\left\{-x\right\} = 1-\left\{x\right\}$ if $x$ is not an integer.

Assuming that $n< ab$ and $n$ is divisible by neither $a$ nor $b$, we have \[ \begin{eqnarray*} p_{(a,b)}(ab-n)&=&\frac{ab-n}{ab}-\left\{\frac{b^{-1}(ab-n)}{a}\right\} - \left\{\frac{a^{-1}(ab-n)}{b}\right\} + 1 \\ &=&2 - \frac{n}{ab} -\left\{-\frac{b^{-1}n}{a}\right\} - \left\{-\frac{a^{-1}n}{b}\right\} \\ &=&-\frac{n}{ab}+\left\{\frac{b^{-1}n}{a}\right\}+ \left\{\frac{a^{-1}n}{b}\right\} \\ &=&1-p_{(a,b)}(n) \\ \end{eqnarray*} \]

In other words, we have \[ p_{(a,b)}(n) + p_{(a,b)}(ab-n) = 1 \]

if $n$ is not divisible by either $a$ or $b$.

Keeping in mind that the restricted partition function is nonnegative, we conclude that when $n< ab$ and $n$ is not divisible by either $a$ or $b$, then exactly one of the integers $n$ or $ab-n$ is representable.

With this observation in hand, we may determine the Frobenius number by considering $n=a+b = 1\cdot a + 1\cdot b$. Therefore, $n=a+b$ is representable and divisible by neither $a$ nor $b$. This means that $ab-(a+b) = ab-a-b$ is not representable. Since we previously saw that $n$ is representable whenever $n> ab-a-b$, we have found the Frobenius number.

If $a$ and $b$ are relatively prime, then the Frobenius number \[g(a,b)=ab-a-b.\]

This is consistent with the earlier example in which we saw that the Frobenius number $g(4,7) = 4\cdot7-4-7 = 17$.

 

Comments?

More than two denominations

Some of what we have done immediately applies when there are more than two denominations of currency. For instance, the restricted partition function is found in precisely the same way; if we have denominations $a$, $b$, and $c$, then \[ p_{\{a,b,c\}}(n) = \hbox{the constant term in} \frac1{(1-z^a)(1-z^b)(1-z^c)z^n}. \]

Proceeding as before, we find: \[ \begin{eqnarray*} p_{\{a,b,c\}}(n)&=&\frac{n^2}{2abc} + \frac n2\left(\frac1{ab} + \frac 1{ac} + \frac1{bc}\right) + \frac 1{12}\left(\frac 3a+\frac3b + \frac 3c + \frac a{bc} + \frac b{ac}+\frac c{ab}\right) \\ & & + \frac 1a\sum_{k=1}^{a-1}\frac1{(1-\zeta_a^{kb})(1-\zeta_a^{kc}) \zeta_a^{kn}} + \frac 1b\sum_{k=1}^{b-1}\frac1{(1-\zeta_b^{kc})(1-\zeta_b^{ka}) \zeta_b^{kn}} \\ & & + \frac 1c\sum_{k=1}^{c-1}\frac1{(1-\zeta_c^{ka})(1-\zeta_c^{kb}) \zeta_c^{kn}} \end{eqnarray*} \]

Given the success we've had in finding the Frobenius number when $d=2$ with rather elementary methods, it seems natural to think that, with some more work, we can find a general formula for the Frobenius number $g(a, b, c)$ when $d=3$. Unfortunately, this problem seems to be much more difficult: there is no general formula known for the Frobenius number when $d\geq 3$.

Worse yet, Ramírez-Alfonsín has shown that solving the Frobenius problem is NP-hard, if we allow a general list of denominations $a_1,a_2,\ldots,a_d$ to be input.

However, Kannan showed that there is an algorithm that completes in polynomial time for any fixed value of $d$, which means that the Frobenius number can be efficiently computed if we fix the number of denominations.

To give an indication of how such an algorithm works, I will present an idea of Nijenhuis that constructs a weighted graph and then computes the Frobenius number by applying Dijkstra's algorithm to find minimal weight paths.

If we have denominations $a_1,a_2,\ldots, a_d$, we form a graph whose vertices are the integers $0,1,2,\ldots,a_1-1$, which may be thought of as the residue classes of $a_1$. There is a directed edge with weight $a_j$ from vertex $v$ to vertex $w$ if $w\equiv v+a_j\bmod{a_1}$, where $j\geq 2$.

For each vertex $v\not\equiv0$, we use Dijkstra's algorithm to find the path from 0 to $v$ having the smallest possible weight, which we denote by $w_v$. It is now relatively straightforward to see that the largest nonrepresentable integer congruent to $v$ is $w_v-a_1$. Therefore, the Frobenius number $g(a_1,a_2,\ldots, a_d)=\max_{v\not\equiv0} w_v-a_1$.

Comments?

Summary

As mentioned previously, it is remarkable that the solution to a counting problem may be found using techniques from calculus. However, this is not the only place that the continuous and discrete come together. This article is adapted from the first chapter of the book Computing the Continuous Discretely, written by Matthias Beck and Sinai Robins, which introduces readers to many beautiful, and sometimes deep, ideas that illustrate this theme.

References

• Matthias Beck, Sinai Robins. Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra. Springer, 2007.

  A very readable book written at the level of an advanced undergraduate or beginning graduate student. There are lots of interesting exercises and open problems.

• Jorge Luis Ramírez-Alfonsín. The Diophantine Frobenius Problem. Oxford University Press, 2006.

  This book provides a thorough introduction to the Frobenius problem as well as much insight into what is currently known.

• James J. Sylvester. On subinvariants; i.e. semi-invariants to binary quantics of an unlimited order. American Journal of Mathematics, 5: 119-136, 1882.

  While it is not clear who first found the expression for the Frobenius number $g(a,b)$, Sylvester's paper indicates that he was likely aware of it.

• Jorge Luis Ramírez-Alfonsín. Complexity of the Frobenius Problem. Combinatorica, 16(1): 143-147, 1996.
   
• Albert Nijenhuis. A minimal-path algorithm for the "money changing problem." American Mathematics Monthly, 86: 832-838, 1979.
   
• Ravi Kannan. Lattice translates of a polytope and the Frobenius problem. Combinatorica, 12(2): 161-177, 1992.
   
• Dale Beihoffer, Jemimah Hendry, Albert Nijenhuis, Stan Wagon. Faster algorithms for Forbenius numbers. Electronic Journal of Combinatorics, 12(1): Research Paper 27, 2005.

  This paper describes the fastest known algorithm for finding Frobenius numbers and includes a comparison with several other algorithms.