Frobenius number for three numbers

Question

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?

Answer 1

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/

Answer 2

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>

Answer 3

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

Answer 4

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

Answer 5

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/

Answer 6

Here is pseudocode for the Bocker-Liptak algorithm:

Let a be the numbers a[1], a[2], ... a[k]
Lay out a[1] tiles (numbered 1 thru a[1]) on which to write numbers
Write 0 on tile 1
for i in [2, ..., k]
    find gcd(a[1], a[i])
    d = gcd(a[1], a[i])
    for starting tile r in [1, ..., d]
        let nn be the smallest number on tiles r, r + d, ...;
        if there are no numbers written on those tiles, go to the next starting tile
        else repeat the following floor(a[1]/d) times
            add a[i] to nn
            let p be nn mod a[1]
            go to tile p
            if there is nothing there, write nn
            else write min(nn, what is there)

When done, subtract a[1] from the largest number written on the tiles: this the
Frobenius number for the given values in `a`.

Here is Python code for the algorithm that I have modified:

    def frobenius_number(*a):
        """
        Return the first number past which all numbers divisible by
        the gcd of the numbers can be made from non-negative multiples
        of positive integers in `a`; also report the gcd of the numbers.

        >>> frobenius_number(6,9,20)
        (43, 1)

        Any number larger than 43 can be created from combinations
        of 6, 9 and 20.

        >>> frobenius_number(20, 44)
        (159, 4)

        Starting at 160, all multiples of 4 can be made from
        combinations of 20 and 44.
        """

        from sympy import igcd

        # modified Bocker-Liptak implementation from https://brg.a2hosted.com/?page_id=563

        def __residue_table(a):
            from collections import defaultdict
            n = defaultdict(None)
            n[0] = 0
            for i in range(1, len(a)):
                d = igcd(a[0], a[i])
                for r in range(d):
                    try: nn = min(n.get(q) for q in range(r, a[0], d) if q in n)
                    except ValueError: continue  # e.g. a = 2,4,5 or 4,6,7
                    for _ in range(a[0] // d):
                        nn += a[i]
                        p = nn % a[0]
                        if n.get(p) is not None:
                            nn = min(nn, n[p])
                        n[p] = nn
            return n

        a = [i for i in a if i]
        if len(a) == 0 or any(i < 0 for i in a):
            raise ValueError
        if len(a) == 1:
            return -(a[0] - 1)
        g = igcd(*a)
        if g != 1:
            n = frobenius_number(*[i // g for i in a])[0]
            return g * (n + 1) - 1, g
        a = sorted(a)
        return max(__residue_table(a).values()) - a[0], 1
```