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_{\phi}(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.
From: Amir Jafari [view email]
[v1]
Tue, 22 Mar 2022 04:44:23 UTC (10 KB)
[v2]
Sun, 6 Sep 2026 03:12:58 UTC (17 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。