The problem is to find the largest number of McNuggets that cannot be bought in exact quantity, given that McNuggets come in packs of 6, 9 and 20. This is called the Frobenius Number, as described in this Numberphile video: How to order 43 Chicken McNuggets
First, we solved Problems 1 and 2 from this problem set: MIT OpenCourseWare Problem Set on Diophantine Equations
Theorem: If it is possible to buy x, x+1, ..., x+5 sets of McNuggets, for some x, then it is possible to buy any number of McNuggets >= x, given that McNuggets come in 6, 9 and 20 packs.
Implementing an exhaustive search for the Frobenius Number using the pseudocode outlined in the problem set was a bit cumbersome, because it requires multiple passes through the nested loops. Let's try a different approach.
The following python code will generate a list of all purchasable amounts with up to 50 coming from any one pack size. We have already shown that 50, 51, 52, 53, 54, 55, and all higher amounts are purchasable. This code is efficient, because it requires only one pass through the three nested loops.
bigList=[]
for Box6 in xrange(0,50,6):
for Box9 in xrange(0,50,9):
for Box20 in xrange(0,50,20):
bigList.append(Box6+Box9+Box20)
print bigList
Unfortunately, this list is a mess. It is unsorted and contains duplicates. Fortunately, the list can be easily sorted:
bigList.sort()
print bigList
Duplicates can be removed by converting the list to a set, since sets contain no duplicates.
bigSet=set(bigList)
print bigSet
This is the set of purchasable amounts, but we really want the set of unpurchasable amounts. We can take advantage of Python Set Operations by subtracting this set from a complete set of numbers of 0 through 49.
completeList = range(50)
completeSet = set(completeList)
print completeSet
Putting everything together...¶
bigList=[] # create an empty list
for Box6 in xrange(0,50,6): # loop over all possible purchasable amounts from a pack of 6
for Box9 in xrange(0,50,9): # loop over all possible purchasable amounts from a pack of 9
for Box20 in xrange(0,50,20): # loop over all possible purchasable amounts from a pack of 20
bigList.append(Box6+Box9+Box20) # put all purchasable amounts found into the list
bigList.sort() # sort the big ugly list
bigSet=set(bigList) # remove duplicates by converting to a set
completeList=range(50) # generate a simple list 0,1,2,...,49
completeSet=set(completeList) # convert simple list to a set
print completeSet-bigSet # print members of completeSet not in bigSet
So this is our final list of unpurchasable amounts. The largest unpurchasable amount is 43.
