Welcome to MathOverflow

Question

6

2

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?

edited May 1 2010 at 5:00

Alon Amit
4,035●15●40

asked May 1 2010 at 1:46

Jernej
952●5●19

2

Note that your use of $b$ for the right hand side of the linear equation is somewhat unfortunate. – Pete L. Clark May 1 2010 at 2:32

Alexey Ustinov · Accepted Answer · 2010-05-05 04:38:02Z UTC

6

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/

edited May 5 2010 at 4:38

answered May 1 2010 at 9:24

Alexey Ustinov
1,356●4●13

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 2010 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 2010 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 2010 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 2010 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 2010 at 6:46

show 1 more comment

Stan Wagon · Answer 2 · 2010-12-15 02:52:40Z UTC

6

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>

answered Dec 15 2010 at 2:52

Stan Wagon
101●1●1

2

Welcome to MathOverflow! – Andrey Rekalo Dec 15 2010 at 13:05

Pete L. Clark · Answer 3 · 2010-05-01 02:28:35Z UTC

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

Alexey Ustinov · Answer 4 · 2010-05-04 11:19:14Z UTC

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

Joseph Malkevitch · Answer 5 · 2010-05-04 16:07:05Z UTC

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/

Frobenius number for three numbers

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

5 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.