Given a list of positive integers $a_1,\ldots,a_n$, the Frobenius coin problem asks for the largest integer $N$ such that the equation

has no solutions where $x_i$ are nonnegative integers. This integer is denoted as $g(a_1,\ldots,a_n)$

A related question asks whether a given $N$ has such a solution. A necessary (albeit not sufficient) condition is that $N$ is divisible by $G = \mathrm{gcd}(a_1,\ldots,a_n)$. However, it can be shown that, if $A = \max_i a_i$, any $N>A^2$ has such a solution iff. $N$ is divisible by $G$^need Thus the Frobenius coin problem is only well defined when $G=1$

These problems are NP-Hard, although they can be solved in pseudo-polynomial time $O(na_1\log(na_1))$¹²

Identities for small $n$

$n=2$

There is a closed-form solution for $n=2$

Furthermore, the number of integers that don't have a solution is given by the formula:

$n=3$

There is no known closed-form solution for $n=3$, although the following equality is known to hold:^need

Problems

• Knapsack in a Globalized World
• Linear Combinations of Semiprimes
• Sums
• LongLongTripDiv1³

See also

• Bézout's identity
• Knapsack problem

External links

• Coin problem