On the Frobenius Coin Problem in Three Variables

Abstract

The three-variable Frobenius coin problem asks for the largest integer that cannot be represented as a non-negative integer combination of three positive integers $a_1<a_2<a_3$ with $\gcd (a_1,a_2,a_3)=1$. We introduce an algorithmic framework based on two synchronized Euclidean-division sequences. The method has arithmetic complexity $O(\log a_1)$, matching the best known logarithmic order for the three-variable problem. We prove that this dependence is asymptotically sharp for the proposed algorithm by constructing an explicit infinite Fibonacci-type family for which Step 2 requires $\frac{1}{2}{\log }_{\varphi }(a_1)+O(1)$ iterations. Hence the worst-case arithmetic complexity of the algorithm is $\Theta (\log a_1)$. We also give a constant-overhead reduction from gcd computation to two evaluations of the three-variable Frobenius function. In addition, the synchronized framework yields an upper bound for the Frobenius number, recovers several known special cases, and provides another proof of the Erdős--Graham bound. The main advantage of the method is its elementary Euclidean structure, which supports both computation and theoretical analysis.