Transcript Frobenius Number for Three Numbers

Frobenius Number
for Three Numbers
By Arash Farahmand
MATH 870
Spring 2007
Coin Exchange Problem


What is the largest amount that cannot be
changed?
First tackled by G. Frobenius (1849-1917) and
J. Sylvester (1814-1897)
N=2


With two coins
Formula: g (n, m) = nm – n – m
Complexity for N > 2



Frobenius numbers by lattice point
enumeration
Polynomial time on average for fixed N
Relatively fast algorithm for lattice reduction
applied to find Frobenius number when N = 3
Algorithm


Step 1. Form the homogeneous basis and then
use lattice reduction to obtain a reduced basis
V
Step 2. Make use of V and the ILP methods to
determine the two axial protoelbows (x1, y1)
and (x2, y2)
Algorithm (continued)


Step 3. If y1 or x2 is zero then the elbow set is
{(x1, 0), (0, y2)};
otherwise it is {(x1, 0), (0, y2), (x1+ x2, y1 + y2)}
Step 4. In all cases the Frobenius number is
max [{(x1, y1 + y2), (x1+ x2, y2} B] - ΣA
References


M. Beck and S. Robins, Computing the
Continuous Discretely, 2006, Springer
S. Wagon, D. Einstein, D. Lichtblau, and A.
Strzenbonski, Frobenius Numbers by Lattice
Point Enumeration,
http://stanwagon.com/public/FrobeniusByLatt
icePoints.pdf , Revised Aug 1, 2006, last
visited February 15, 2007