Coin problem

In mathematics, the coin problem (also referred to as the Frobenius coin problem or Frobenius problem, after the mathematician Ferdinand Frobenius) is a mathematical problem that asks for the largest monetary amount that cannot be obtained using only coins of specified denominations. For example, the largest amount that cannot be obtained using only coins of 3 and 5 units is 7 units. The solution to this problem for a given set of coin denominations is called the Frobenius number of the set. The Frobenius number exists as long as the set of coin denominations is setwise coprime. There is an explicit formula for the Frobenius number when there are only two different coin denominations, x {\displaystyle x} and y {\displaystyle y} , where the greatest common divisor of these two numbers is 1: x y − x − y {\displaystyle xy-x-y} . If the number of coin denominations is three or more, no explicit formula is known. However, for any fixed number of coin denominations, there is an algorithm for computing the Frobenius number in polynomial time (in the logarithms of the coin denominations forming an input). No known algorithm is polynomial time in the number of coin denominations, and the general problem, where the number of coin denominations may be as large as desired, is NP-hard.