View source for Frobenius problem

{{TEX|done}}
''coin-change problem''

Given $n$ natural numbers $a_1,\ldots,a_n$ with greatest common divisor $1$, find the largest natural number that is not expressible as a linear non-negative integer combination of the $a_1,\ldots,a_n$.

For $n=2$ the answer is given by $a_1a_2-a_1-a_2$. The general problem is $\mathcal{NP}$-hard.

For a fixed $n$ there is a polynomial-time algorithm to solve the Frobenius problem, [[#References|[a1]]].

The Frobenius problem is related to the study of maximal lattice-point-free convex bodies (in the [[geometry of numbers]]), [[#References|[a2]]].

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  R. Kannan,   "Lattice translates of a polytope and the Frobenius problem"  ''Combinatorica'' , '''12'''  (1992)  pp. 161–172</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  L. Lovász,   "Geometry of numbers and integer programming"  M. Iri (ed.)  K. Tanabe (ed.) , ''Mathematical Programming'' , Kluwer Acad. Publ.  (1989)  pp. 177–202</TD></TR>
</table>