12
$\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$
3
  • 2
    $\begingroup$ Note that your use of $b$ for the right hand side of the linear equation is somewhat unfortunate. $\endgroup$ – Pete L. Clark May 1 '10 at 2:32
  • 2
    $\begingroup$ 2016 update: Amitabha Tripathi has an article in press called "Formulae for the Frobenius number in three variables" to be published in the Journal of Number Theory. I haven't seen it yet so I can't compare it to the Einstein-Lichtblau-Strzebonski-Wagon algorithm. Video abstract here: youtube.com/watch?v=dv0GSy2MGzw $\endgroup$ – Charles Aug 28 '16 at 2:01
  • 1
    $\begingroup$ @Charles the Tripathi paper is now available at web.iitd.ac.in/~atripath/publications/FP_3-var.pdf (J. Number Theory 170 (2017) 368-389) and it was discussed very briefly at mathoverflow.net/questions/292152/… $\endgroup$ – Gerry Myerson Nov 23 '19 at 3:07
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 '10 at 14:18
  • 2
    $\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$ – Alexey Ustinov May 4 '10 at 11:33
  • 2
    $\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$ – Alexey Ustinov May 4 '10 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 '10 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$ – Alexey Ustinov Dec 19 '10 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 '10 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$
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$ – Gerry Myerson Nov 23 '19 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 '19 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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