13
$\begingroup$

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?

$\endgroup$
2

6 Answers 6

10
$\begingroup$

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/

$\endgroup$
6
  • 1
    $\begingroup$ 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$? $\endgroup$
    – Jernej
    May 1, 2010 at 14:18
  • 3
    $\begingroup$ 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$. $\endgroup$ May 4, 2010 at 11:33
  • 3
    $\begingroup$ 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$. $\endgroup$ May 4, 2010 at 11:36
  • 3
    $\begingroup$ 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 $\endgroup$
    – Stan Wagon
    Dec 18, 2010 at 16:02
  • 1
    $\begingroup$ 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? $\endgroup$ Dec 19, 2010 at 6:46
10
$\begingroup$

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>

$\endgroup$
0
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Yeah. I've seen that one mentioned in a few papers. The only problem seem to be that it is not freely accessible online. $\endgroup$
    – Jernej
    May 1, 2010 at 2:25
2
$\begingroup$

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/

$\endgroup$
1
  • $\begingroup$ The link to the article at springerlink.com is broken. I'm also not able to find any copy saved on the Wayback Machine. $\endgroup$ Jun 13, 2022 at 6:39
0
$\begingroup$

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
```
$\endgroup$
2
  • 1
    $\begingroup$ I don't think anyone else has so much as mentioned any Bocker-Liptak algorithm. Can you add a few words about when and where it was published, maybe a plain-English summary of how it works, some idea of how it compares with the other algorithms that we've seen here? We aren't all fluent in Python. $\endgroup$ Nov 23, 2019 at 3:02
  • $\begingroup$ This algorithm was published in Algorithmica in 2007. A glimpse is available here with other references to more recent work on this computation: link.springer.com/article/10.1007%2Fs00453-007-0162-8 . It is O(k*a1). It is similar to the Eratosthenes method of finding primes; I have also seen it referred to as a round-robin approach. I will annotate the code. $\endgroup$
    – smichr
    Nov 23, 2019 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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