Diophantine Equation

Posted by lakshmi on Stack Overflow See other posts from Stack Overflow or by lakshmi
Published on 2010-06-16T05:22:37Z Indexed on 2010/06/16 5:32 UTC
Read the original article Hit count: 468

Filed under:

Show that it is possible to buy exactly 50, 51, 52, 53, 54, and 55 McNuggets, by finding solutions to the Diophantine equation. You can solve this in your head, using paper and pencil, or writing a program. However you chose to solve this problem, list the combinations of 6, 9 and 20 packs of McNuggets you need to buy in order to get each of the exact amounts. Given that it is possible to buy sets of 50, 51, 52, 53, 54 or 55 McNuggets by combinations of 6, 9 and 20 packs, show that it is possible to buy 56, 57,..., 65 McNuggets. In other words, show how, given solutions for 50-55, one can derive solutions for 56-65.python

Diophantine Equation

Posted by swapnika on Stack Overflow See other posts from Stack Overflow or by swapnika
Published on 2010-06-16T04:37:20Z Indexed on 2010/06/16 4:42 UTC
Read the original article Hit count: 468

Filed under:

python

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

Developer IT