From: shallit@graceland.uwaterloo.ca (Jeffrey Shallit)
Subject: Re: ax+by+cz for nonnegative integers x, y, and z
Date: 4 Nov 00 17:56:47 GMT
Newsgroups: sci.math.numberthy
Summary: [missing]

> From: Hojoo Lee <leehojoo@hotmail.com>
> Subject:      ax+by+cz for nonnegative integers x, y, and z
> To: NMBRTHRY@LISTSERV.NODAK.EDU
>
> It is well-known and is not hard to show that
> "if a>0, b>0, and gcd(a,b)=1, then ab-a-b is the largest integer not
> representable as ax+by (x>=0 , y>=0)"
>
> Please, let me know recent results or references
> about the following open problem ;
>
> "Let a, b, and c be three positive integers satisfying gcd(a,b,c)=1.
> Determine the largest integer not representable as ax+by+cz for some
> nonnegative integers x, y, and z."
>
> Thanking you,
>
> -Lee, Hojoo (leehojoo@hotmail.com)

This is known as the Frobenius problem.  Fast algorithms are known
for three numbers, but the problem for an arbitrary number of numbers
is known to be NP-hard, and therefore there is likely to be no
simple formula.  Even in the case of three numbers the formula is
not simple.

Here are some relevant references.  These are taken from a BibTex bibliography
of the Frobenius problem I have with many entries.

@string{JRMS = "J. Ramanujan Math. Soc."}
@string{JNT = "J. Number Theory"}
@string{JFRAM = {J. Reine Angew. Math.}}

@article{Rodseth:1978,
        key = "{R\"odseth} 1978",
        author = "{\"O.} J. {R\"odseth}",
        title = "On a linear {Diophantine} problem of {Frobenius}",
        journal = JFRAM,
        volume = 301,
        year = 1978,
        pages = "171-178"}

@article{Rodseth:1979,
        key = "{R\"odseth} 1979",
        author = "{\"O. J. R\"odseth}",
        title = "On a linear diophantine problem of {Frobenius}. {II}",
        journal = JFRAM,
        volume = "307/308",
        year = 1979,
        pages = "431-440"}

@article{Hujter&Vizvari:1987,
        key = "Hujter and Vizvari 1987",
        author = "M. Hujter and B. Vizvari",
        title = "The exact solutions to the {Frobenius} problem with three variables",
        journal = JRMS,
        volume = 2,
        year = 1987,
        pages = "117-143"}

@article{Davison:1994,
        key = "Davison 1994",
        author = "J. L. Davison",
        title = "On the linear Diophantine problem of Frobenius",
        journal = JNT,
        volume = 48,
        year = 1994,
        pages = "353-363"}

@article{Ramirez-Alfonsin:1996,
        key = "Ram\'{\i}rez-Alfons\'{\i}n 1996",
        author = "J. L. Ram\'{\i}rez-Alfons\'{\i}n",
        title = "Complexity of the {Frobenius} problem",
        journal = "Combinatorica",
        volume = 16,
        year = 1966,
        pages = "143-147"}

@article{Kannan:1992,
        key = "Kannan 1992",
        author = "R. Kannan",
        title = "Lattice translates of a polytope and the {Frobenius}
problem",
        journal = "Combinatorica",
        volume = 12,
        year = 1992,
        pages = "161-177"}