Generalization of the Rødseth's algorithm for the Diophantine Frobenius Problem with n=3

Given a set (a₁, a₂..., a_n) of positive integers (a_i >= 1), the Frobenius Problem looks for the largest number g that cannot be represented by the equation g = a₁·x₁ + a₂·x₂ +... + a_n·x_n, with x_i integers >= 0. g is called the Frobenius number of the set. [1]

This problem is also known as the Coin Problem, where is asked the largest monetary amount that cannot be obtained using only coins of specified denominations.

The Frobenius Problem has applications in diverse areas as sort methods analysis, Petri Nets, tilings, random vectors generation, etc. [1]

A particular case is known as the Mc Nuggets Problem: which is the largest number that cannot be obtained as the sum of pieces in an order of any number of McDonald's Chicken McNuggets boxes, which originally came in quantities of 6, 9 and 20? [2]

If the greatest common divisor of the set is grater than 1, the Frobenius number of the set is undefined. [3]

If n = 2, g(a₁, a₂) = a₁·a₂ - a₁ - a₂. [4]

The general problem with n variable is NP-hard under Turing reductions. [1] That's why there is a variety of algorithms and formulae that try to avoid the brute force approach.

For n = 3 and a₁, a₂, a₃ pairwise coprime integers (greatest common divisor = 1) there is an algorithm by Ø. J. Rødseth than works well on average (probably O(log a₂)), even if in the worst case can take O(a₁ + log a₂) operations. [1]

This algorithm is explained in a few places [1][5] but I couldn't find an implementation in code and I ran into troubles trying to apply proposed generalization when the numbers in the set are not pairwise coprime integers, so I want to share my implementation in Rust.

In this implementation let's define g(A) = -1 when any a_i = 1 (which makes sense since a_i = 1 is all you need to represent any positive integer and 0 can always be represented, so -1 is the largest integer that cannot be obtained), and use this generalization:

d12 = gcd(a₁, a₂);
d13 = gcd(a₁ / d12, a₃);
d23 = gcd(a₂ / d12, a₃ / d13);
a' = (a₁ / d12 / d13, a₂ / d12 / d23, a₃ / d13 / d23)
r = Rødseth algorithm applied to a'
g(a₁, a₂, a₃) = r * d12 * d13 * d23 + a₁ * (d23 - 1) + a₂ * (d13 - 1) + a₃ * (d12 - 1)

This works with any set of positive integers that have a defined Frobenius number (i.e. gcd(a₁, a₂, a₃) = 1).

Examples:
a = (12, 14, 17)
a'= (6, 7, 17)
d12 = 2, d13 = 1, d23 = 1
r = 22
g = 22 * 2 + 12 * 0 + 14 * 0 + 17 * 1 = 61

a = (12, 13, 34)
a'= (6, 13, 17)
d12 = 1, d13 = 2, d23 = 1
r = 33
g = 33 * 2 + 12 * 0 + 13 * 1 + 34 * 0 = 79

a = (5, 9, 21)
a'= (3, 5, 7)
d12 = 1, d13 = 1, d23 = 3
r = 4
g = 4 * 3 + 5 * 2 + 9 * 0 + 21 * 0 = 22

a = (6, 9, 20)
a'= (1, 3, 10)
d12 = 3, d13 = 2, d23 = 1
r = -1
g = -1 * 6 + 6 * 0 + 9 * 1 + 20 * 2 = 43

a = (582795988, 1753241221, 6814151015)
a'= (582795988, 1753241221, 6814151015)
d12 = 1, d13 = 1, d23 = 1
r = 173685179295403
g = 173685179295403 * 1 + 582795988 * 0 + 1753241221 * 0 + 6814151015 * 0 = 173685179295403

a = (4, 16, 30)
g = undefined (gcd(a) = 2)

a = (12, 12, 13)
a'= (1, 1, 13)
d12 = 12, d13 = 1, d23 = 1
r = -1
g = -1 * 12 + 12 * 0 + 12 * 0 + 13 * 11 = 131

a = (1, 6, 15)
a'= (1, 2, 5)
d12 = 1, d13 = 1, d23 = 3
r = -1
g = -1 * 3 + 1 * 2 + 6 * 0 + 15 * 0 = -1


Working code:

Rust playground


[1] https://global.oup.com/academic/product/the-diophantine-frobenius-problem-9780198568209
[2] https://en.wikipedia.org/wiki/Coin_problem#McNugget_numbers
[3] https://en.wikipedia.org/wiki/Schur%27s_theorem#Combinatorics
[4] https://www.jstor.org/stable/2369536
[5] http://people.reed.edu/~iswanson/LepilovORourkeSwanson.pdf