Coin Problem

Let there be n>=2 integers 0<a_1<...<a_n with GCD(a_1,a_2,...,a_n)=1. The values a_i represent the denominations of n different coins, where these denominations have greatest common divisor of 1. The sums of money that can be represented using the given coins are then given by


where the x_i are nonnegative integers giving the numbers of each coin used. If a_1=1, it is obviously possibly to represent any quantity of money N. However, in the general case, only some quantities N can be produced. For example, if the allowed coins are (2,5,10), it is impossible to represent N=1 and 3, although all other quantities can be represented.

Determining the function g(a_1,a_2,...,a_n) giving the greatest N=g(a_1,a_2,...,a_n) for which there is no solution is called the coin problem, or sometimes the money-changing problem. The largest such N for a given problem is called the Frobenius number g(a_1,a_2,...).

The result


(Nijenhuis and Wilf 1972) is mathematical folklore. The total number of such nonrepresentable amounts is given by


The largest nonrepresentable amounts g(a_1,a_2) for two coins with denominations a_1 and a_2 are summarized below.


Fast algorithms are also known for three numbers, but the more general problem for an arbitrary number of numbers is known to be NP-hard if n is fixed (Kannan 1992) or n is variable (Ramírez-Alfonsín 1996).

There is no closed-form solution for n=3, although a semi-explicit solution is known which allows values to be computed quickly ((Selmer and Beyer 1978, Rödseth 1978, Greenberg 1988; Beck and Robins 2006). Values for small a_i are summarized below.


No closed-form solution is known for n>4.

See also

Frobenius Number, Greedy Algorithm, Knapsack Problem, Postage Stamp Problem, Subset Sum Problem

Explore with Wolfram|Alpha


Beck, M. and Robins, S. "The Coin-Exchange Problem of Frobenius." §C1 in Computing the Continuous Discretely. New York: Springer, pp. 3-23, 2006., E. R.; Conway, J. H; and Guy, R. K. Winning Ways for Your Mathematical Plays, Vol. 2: Games in Particular. London: Academic Press, 1982.Brauer, A. "On a Problem of Partitions." Amer. J. Math. 64, 299-312, 1942.Brauer, A. and Seelbinder, B. M. "On a Problem of Partitions. II." Amer. J. Math. 76, 343-346, 1954.Davison, J. L. "On the Linear Diophantine Problem of Frobenius." J. Number Th. 48, 353-363, 1994.Greenberg, H. "Solution to a Linear Diophantine Equation for Nonnegative Integers." J. Algorithms 9, 343-353, 1988.Guy, R. K. "The Money-Changing Problem." §C7 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 113-114, 1994.Kannan, R. "Lattice Translates of a Polytope and the Frobenius Problem." Combinatorica 12, 161-177, 1992.Nabiyev, V. V. Algorithms: From Theory to Applications. Ankara, Turkey: Seckin, p. 799, 2007.Nijenhuis, A. "A Minimal-Path Algorithm for the 'Money Changing Problem.' " Amer. Math. Monthly 86, 832-835, 1979.Nijenhuis, A. and Wilf, H. S. "Representations of Integers by Linear Forms in Nonnegative Integers." J. Number Th. 4, 98-106, 1972.Ramírez-Alfonsín, J. L. "Complexity of the Frobenius Problem." Combinatorica 16, 143-147, 1996.Ramírez-Alfonsín, J. L. The Diophantine Frobenius Problem. Oxford, England: Oxford University Press, 2005.Rødseth, Ø. J. "On a Linear Diophantine Problem of Frobenius." J. reine angew. Math. 301, 171-178, 1978.Rødseth, Ø. J. "On a Linear Diophantine Problem of Frobenius. II." J. reine angew. Math. 307/308, 431-440, 1979.Selmer, E. S. "The Linear Diophantine Problem of Frobenius." J. reine angew. Math. 293/294, 1-17, 1977.Selmer, E. S. and Beyer, Ö. "On the Linear Diophantine Problem of Frobenius in Three Variables." J. reine angew. Math. 301, 161-170, 1978.Sylvester, J. J. "Question 7382." Mathematical Questions from the Educational Times 41, 21, 1884. Wagon, S. "Greedy Coins.", H. "A Circle of Lights Algorithm for the 'Money Changing Problem.' " Amer. Math. Monthly 85, 562-565, 1978.

Referenced on Wolfram|Alpha

Coin Problem

Cite this as:

Weisstein, Eric W. "Coin Problem." From MathWorld--A Wolfram Web Resource.

Subject classifications