On the Frobenius Coin Problem in Three Variables

Abstract

The Frobenius coin problem in three variables, for three positive relatively prime integers $a_1<a_2<a_3$ asks to find the largest number not representable as $a_1{x}_1+a_2{x}_2+a_3{x}_3$ with non-negative integer coefficients $x_1$, $x_2$ and $x_3$. In this article, we present a new algorithm to solve this problem that is faster and in our belief simpler than all existing algorithms and runs in $\mbox{O}(\log a_1)$ steps.