FROBENIUS
Routines for the Frobenius Problem

FROBENIUS is a collection of Mathematica routines for the solution of Frobenius's problem.

Frobenius's problem assumes that there are N denominations of coins, A₁ through A_N, and asks for the largest quantity that cannot be formed using any combination of the coins.

It is assumed that the denominations are all positive integers.

The problem is "impossible" if the denominations have a common factor greater than 1 - impossible in the sense that in this case there are an infinite number of quantitities that cannot be formed. On the other hand, if the denominations do not all share a common factor greater than 1, then there is always a finite solution, that is, a largest quantity that cannot be formed by the denominations. In this case, the value is called the Frobenius number, and symbolized by g(A₁,A₂,...A_N).

The case of two denominations is easy:

g(a,b) = a*b - a - b

In an example inspired by the "denominations" of McDonald's MacNuggets, there are 3 denominations, 6, 9, and 20, and it can be shown that the number 43 is the largest value that cannot be formed by combinations of these denominations.

Note that Mathematica has a built in command that can compute the Frobenius number:

FrobeniusNumber [ { 6, 9, 20 } ]

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Reference:

1. Dale Beihoffer, Jemimah Hendry, Albert Nijenhuis, Stan Wagon,
   Faster Algorithms for Frobenius Numbers,
   The Electronic Journal of Combinatorics,
   Volume 12, 2005, #R27.
2. Robert Owens,
   An Algorithm to Solve the Frobenius Problem,
   Mathematics Magazine,
   Volume 76, Number 4, October 2003, pages 264-275.

Source Code:

• bfd.nb, the BFD algorithm, the breadth-first-decreasing algorithm.

Examples and Tests:

• bfd_example.nb, an example in which the BFD algorithm is used to determine several Frobenius numbers.

You can go up one level to the Mathematica packages and notebooks.