On Frobenius numbers in three variables

Abstract

Given a set of relatively prime positive integers $\{a_1,a_2,\ldots, a_n\}$, after some point all positive integers are representable as a linear combination of the set with nonnegative coefficients. Which integer is the last one not so representable is the Frobenius problem, or the Frobenius stamp problem, and the number in question the Frobenius number of the set. While the two-variable solution is widely known, and the general solution is NP-hard, there have been several algorithmic solutions of the three-variable problem. Here we present a new bound for the Frobenius number of most relatively prime triples.