An Introduction to Frobenius Numbers

Welcome to my blog! I recently learned about Frobenius Numbers, and I thought they were super interesting to share with my readers as a first post :)

If we suppose that x_n are positive integers such that the greatest common factor of x₁, x₂, x₃, …, and x_n is 1. The Frobenius Number, often expressed by g(x₁, x₂, x₃, …, x_n), is the largest positive integer, y, such that a₁x₁ + a₂x₂ + a₃x₃ + … + a_nx_n = y has no nonnegative solution.

For when there are two numbers, the greatest number y that works here will be x₁x₂-x₁-x₂, or (x₁-1)(x₂-1)-1.

One rather popular example of this problem is the McNugget problem where mathematicians wanted to find the greatest possible number that could not be expressed when buying boxes of chicken nuggets from McDonalds, since they came in box sizes of 6, 9, or 20.

To solve this, we can look at 6 and 9 together. We’ll have 6x+9y=k, or 3(2x+3y). This means that we have to expel all numbers of 3 since they can be created by 6 and 9. Note that 2x+3y cannot be equal to 1. Now if we just add one 20, we’ll have that 3(2x+3y)+20, which can be factored into 3(2x+3y+6)+2, which means that any number two more than a multiple of 3 can also be created. Again, note that 2x+3y+6 cannot be equal to 7 in this case since the value which is impossible to reach of 2x+3y is 1. Now, we want to see if reaching a number that is one more than a multiple of 3 is possible, in which we can add another 20 to our equation. We will now have, 3(2x+3y+6)+22, which can then be factored into 3(2x+3y+13)+1. We can then see that the value of 2x+3y+13 cannot be 14. This will be our solution to the problem where if we plug this in, we’ll have our answer of 43.

Funny enough, McDonalds added another possible combination of box sizes you could order to bypass this!

There are formulas for finding Frobenius numbers where there were two or three numbers, in addition to when the numbers were an arithmetic or geometric sequence, but beyond that none were found.