How to solve Frobneius problem for 3 integers a,b,c? Given gcd(a,b,c)=1 , a<b<c.

Question

Frobneius problem is to find the greatest integer that cannot be represented as linear combination of integers a,b,c,...... The problem for 2 integers a and b is solved easily. But for 3 integers, is there any formula? Or algorithm?I searched and found that it is of form bx+cy-a, but i am not able to understand how to find the solution. If algorithm exists, it would be better if implemented in c++. :)

Answer 1

According to wikipedia no solution is known.

However, `√(abc) - a - b - c` is a lower bound and `min(a,b,c) max(a,b,c) - min(a,b,c) - max(a,b,c)` is an upper bound, so you could check all the numbers in between.

Answer 2

Can you suggest a way to check those nos.? Thanks.