algorithmnumber-theorycoin-changediophantine

Algorithms to compute Frobenius Numbers of a set of positive integers


Frobenius numbers of a set exist iff the gcd of the numbers of the set is 1. Given a set of positive integers with at most 10 elements such that the gcd of all the elements is 1, how can we compute the Frobenius number of the set?

Here is the link to the original problem: https://icpcarchive.ecs.baylor.edu/external/62/6298.pdf Sylvester's formula can be used to find the Frobenius number of a set of 2 elements.


Solution

  • There are quite a few algorithms around for this, but the best option for you is probably the one in this 2004 paper by Bocker and Liptak. The pseudocode can be found on p968, though it's worth reading through the paper because it's quite a neat little algorithm.