Skip to content
Omnikalc

Frobenius coin problem calculator

Enter two coin values or package sizes to get the largest amount that cannot be formed, how many amounts cannot be formed, the amount from which every total is possible and whether the two values are coprime.

Updated on
Your inputs

Value out of range

Value out of range

Results

Largest amount that cannot be made (Frobenius number)

31

Number of amounts that cannot be made

16

Every amount from this value on can be made (conductor)

32

Greatest common divisor of the two values
1
Coprime (1 = yes, 0 = no)
1
Least common multiple
45

The Frobenius coin problem calculator gives the largest amount that cannot be made with two coin values or package sizes, the number of amounts that cannot be made, the conductor from which everything is possible and whether the two values are coprime.

How the calculation works

  • Enter the two values, such as coin values, stamp values or pack sizes.
  • The calculator finds their greatest common divisor to check they are coprime.
  • Read the Frobenius number, the count of impossible amounts and the conductor.

Example

With values of 9 and 5, the greatest common divisor is 1 (coprime flag 1), so the largest amount that cannot be made is 31. There are 16 amounts that cannot be made, and every amount from 32 on can be. The least common multiple is 45.

Why it matters

The calculator helps students, teachers, puzzle fans, cashiers and planners who want to know which totals can be paid with two coin or stamp values, or which quantities can be ordered with two pack sizes, and why large totals always work.

Good to know

Use whole numbers from 2 to 600. If the values are not coprime, divide both by their greatest common divisor first and treat the problem in the new units, since only multiples of the divisor can be made. The formula is for exactly two values, so for three or more you need a computer search. The number of impossible amounts does not include zero, which is always possible with no coins. For a quick check by hand, list the multiples of the smaller value and add the larger one repeatedly: the first run of consecutive possible amounts as long as the smaller value marks the point from which everything works.

The GCD and LCM calculator finds divisors and multiples, the coin jar calculator counts coins, the prime number theorem calculator estimates primes and the polygonal numbers calculator explores number patterns.

Frequently asked questions

What is the Frobenius coin problem?

It asks for the largest amount of money that cannot be paid exactly with coins of given values, used as many times as needed. With only two coprime values a and b, the answer is the Frobenius number a × b − a − b, known since Sylvester in 1882. Above this amount, every total can be made.

Why do the values have to be coprime?

If the two values share a common divisor, every amount made from them is a multiple of it, so infinitely many amounts are impossible and there is no largest one. The calculator then shows zero for the Frobenius number and the other results. It reports the greatest common divisor so you can check it.

How many amounts are impossible?

Sylvester showed that exactly (a − 1)(b − 1) / 2 positive amounts cannot be made. For 5 and 9 there are 16 of them, and the largest is 31. Exactly half of the amounts from 0 to the conductor (a − 1)(b − 1) = 32 are possible, and all amounts beyond it.

Where does it appear?

It describes the chicken nuggets problem, where packs of 6, 9 and 20 cannot make some numbers, stamps and postage, change-making and the largest unreachable total in scheduling problems. For three or more values there is no simple closed formula, and algorithms are needed.

Was this calculator helpful?

Thanks for your feedback!

Results are estimates provided for information purposes. They do not replace professional advice.