## Frobenius Numbers – Round Robin Algorithm

September 20, 2010 at 14:50 (algorithm, java, math.NT)

Frobenius numbers are solutions to the coin problem. Let $\displaystyle 0 be coin denominations; what is the smallest sum of money that cannot be obtained using these coins? More formally, define the Frobenius number $\displaystyle g(a_1,\,\ldots\,,a_n)$ as the greatest number that is not a linear combination $\sum_{i=1}^n x_ia_i$ with $\displaystyle 0 \le x_i \in \mathbb{Z}$. The Frobenius number exists if and only if $\displaystyle a_1 > 1$ and $\displaystyle \gcd(a_1,\,\ldots\,,a_n)=1$. A special case of Frobenius numbers involves the interestingly named McNugget numbers, and there is a well-known formula when $\displaystyle n=2$ given by $\displaystyle g(a_1,a_2)=a_1a_2-a_1-a_2$ sometimes known as the Chicken McNugget Theorem.

In the article “The Money Changing Problem revisited: Computing the Frobenius number in time O(ka1)” (PDF link), published in 2005 by Sebastian Böcker & Zsuzsanna Lipták, a beautiful algorithm known as the round robin algorithm for finding Frobenius numbers with potentially large $\displaystyle n$ is described. Here is a Java implementation I wrote a a little while ago; I can no longer remember under what circumstances integer overflow would occur, but since infinity is represented as -1, the program can be easily rewritten with long or BigInteger if desired. Note that frobenius() does not enforce that the input array be sorted ascending, and also the improvements discussed on page 5 of the article are not implemented.

Another interesting approach involving circulant graphs can be found in “Faster Algorithms for Frobenius Numbers” (PDF link), published by Dale Beihoffer, et al., also in 2005.

import java.util.Arrays;

public class FrobeniusNums {
public static void main(String[] args) {
int[] mcNug = {6, 9, 20};
System.out.println(frobenius(mcNug));
}

static int frobenius(int[] nums) {
int[] ns = new int[nums[0]];
Arrays.fill(ns, -1);
ns[0] = 0;
for (int i = 1; i < nums.length; i++) {
int d = gcd(nums[0], nums[i]);
for (int r = 0; r < d; r++) {
int n = -1;
if (r == 0)
n = 0;
else {
int q = r;
while (q < nums[0]) {
if (ns[q] != -1 && (ns[q] < n || n == -1))
n = ns[q];
q += d;
}
}
if (n != -1)
for (int j = 0; j < nums[0] / d; j++) {
n += nums[i];
int p = n % nums[0];
if (ns[p] != -1 && (ns[p] < n || n == -1))
n = ns[p];
ns[p] = n;
}
}
}
int max = 0;
for (int i = 0; i < nums[0]; i++)
if (ns[i] == -1 || ns[i] > max)
max = ns[i];
if (max == -1) return -1;
return max - nums[0];
}

static int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
}