Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given integers $a,b,c$ such that $\gcd(a,b,c) = 1$, it is well known that there exists only a finite set of numbers $n$ such that $n$ is not expressible as $ax+by+cz$ for non negative integers $x$,$y$,$z$.

It is also known that there exists a quadratic time algorithm for finding the maximal such $n$. However I was not able to spot the paper covering the algorithm.

Anybody happens to know the algorithm and/or a (free) reference to it?

share|improve this question
2  
Note that your use of $b$ for the right hand side of the linear equation is somewhat unfortunate. –  Pete L. Clark May 1 '10 at 2:32

5 Answers 5

up vote 6 down vote accepted

Simple algoritm based on continued fractions was proposed by Rödseth, O. J. On a linear Diophantine problem of Frobenius J. Reine Angew. Math., 1978, 301, 171-178

All algorithm are described in Ramrez Alfonsn, J. L. The Diophantine Frobenius problem Oxford University Press, 2005

I think that Mathematica uses Rödseth's algoritm http://demonstrations.wolfram.com/PositiveFrobeniusNumbersOfThreeArguments/

share|improve this answer
1  
The algorithm can be found here: books.google.com/… The first line of the algorithm computes $s_0$ such that $s_0a_2 = a_3 \mod a_1$ given $1 \leq a_1 < a_2 <a_3$ such that $gcd(a_1,a_2,a_3) = 1$. Am I missing something or is not always possible to compute $s_0$? For example for $6,10,15$? –  Jernej May 1 '10 at 14:18
1  
First of all you must use Johnson's formula. For modified Frobenius number $f(a,b,c)=g(a,b,c)+a+b+c$ it gives $f(a,b,c)=d f(a/d,b/d,c)$. It allows to reduce calculation of $f(a,b,c)$ to the case $(a,b)=(a,c)=(b,c)=1$. –  Alexey Ustinov May 4 '10 at 11:33
1  
For example $f(6,10,15)=2f(3,5,15)=6f(1,5,5)=30f(1,1,1)=60$, $g(6,10,15)=60-6-10-15=29$. –  Alexey Ustinov May 4 '10 at 11:36
1  
Mathematica does not use Rodseth. It uses the very fast algorithm described in our paper in INTEGERS and cited in my answer. This works even for 10000-digit or longer numbers. I believe the algorithm's complexity is "softly linear": O(n^(1+epsilon)). THe specific case of n = 3 is discussed in detail in our paper. Stan Wagon –  Stan Wagon Dec 18 '10 at 16:02
1  
It is strange, because for $n=3$ Rodseth is just extended GCD algorithm. In the worst case it requares $O(\log^2 N)$ operations (and it is known that comlexity can be reduced to $O(\log^{1+\epsilon} N)$). Is your algorithm faster? –  Alexey Ustinov Dec 19 '10 at 6:46

This is addressed in our paper

Frobenius numbers by lattice point enumeration, David Einstein, Daniel Lichtblau, Adam Strzebonski, and Stan Wagon, INTEGERS, 7 (2007) #A15, 63 pp. <http://www.integers-ejcnt.org/vol7.html>

share|improve this answer
2  
Welcome to MathOverflow! –  Andrey Rekalo Dec 15 '10 at 13:05

The following paper seems to be the first to do what you want:

MR0955143 (89j:11122) Greenberg, Harold(1-CUNY2-S) Solution to a linear Diophantine equation for nonnegative integers. J. Algorithms 9 (1988), no. 3, 343--353.

$ $

The paper contains a fundamental improvement in the theory of linear Diophantine equations with three variables. Let $1 < a< b < c $ and $L$ be positive integers. Following the results of \n O. J. Rødseth\en [J. Reine Angew. Math. 301 (1978), 171--178; MR0557016 (58 #27741)] the author gives an algorithm using only $O(\log a)$ steps to generate a nonnegative solution of the linear Diophantine equation $ax+by+cz=L$. Applying this algorithm the author provides us with another algorithm, requiring $O(\log a)$ steps as well, to solve the Frobenius problem with three variables, i.e., to determine the number $\max\{L\in\mathbb{Z} \ | \ \nexists (x,y,z)\in \mathbb{Z}_+^3,\ ax+by+cz=L\}$ assuming that $\operatorname{gcd}(a,b,c)=1$. (Mathscinet review by Béla Vizvári)

I couldn't myself get my hands on a copy of this paper. The same holds for a 1994 J. Number Theory paper of J.L. Davison, which also gives a quadratic algorithm for computing the Frobenius number in the case of $3$ weights.

The most relevant publically available thing I could find (which seems pretty relevant, although I didn't look to see exactly what they say about the $n = 3$ case as opposed to the general case) is a 2005 paper of Beihoffer, Hendry, Nijenhuis and Wagon published in the Electronic Journal of Combinatorics:

http://www.combinatorics.org/Volume_12/Abstracts/v12i1r27.html

share|improve this answer
    
Yeah. I've seen that one mentioned in a few papers. The only problem seem to be that it is not freely accessible online. –  Jernej May 1 '10 at 2:25

Rödseth formula for Frobenius numbers is good not only for computation. It allows to find weak asymptotic for Frobenius numbers with three arguments and density function for normalized Frobenius numbers.

A. V. Ustinov, “The solution of Arnold's problem on the weak asymptotics of Frobenius numbers with three arguments”, Mat. Sb., 200:4 (2009), 131–160

Shchur, V.; Sinai, Y.; Ustinov, A. Limiting distribution of Frobenius numbers for n = 3 Journal of Number Theory, 2009, 129, 2778–2789

share|improve this answer

Several expository papers about the Frobenius problem and its generalizations can be found on Jeffrey Shallit's web page:

http://www.cs.uwaterloo.ca/~shallit/talks.html

and a more technical journal article is linked here:

http://www.springerlink.com/content/655j4t10575052h7/

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.