Diophantine Equation
- by swapnika
Write an iterative program that finds the largest number of McNuggets that cannot be bought in exact quantity. Your program should print the answer in the following format (where the correct number is provided in place of n):
"Largest number of McNuggets that cannot be bought in exact quantity: n"
Hints:
Hypothesize possible instances of numbers of McNuggets that cannot be purchased exactly, starting with 1
For each possible instance, called n,
1. Test if there exists non-negative integers a, b, and c, such that 6a+9b+20c = n. (This can be done by looking at all feasible combinations of a, b, and c)
2. If not, n cannot be bought in exact quantity, save n
When you have found six consecutive values of n that in fact pass the test of having an exact solution, the last answer that was saved (not the last value of n that had a solution) is the correct answer, since you know by the theorem that any amount larger can also be bought in exact quantity
