McDonald's sells Chicken McNuggets only in packages of 6, 9 or 20. What is the largest number of McNuggets that cannot be bought exactly?

Question

Question is from MIT OCW Course Number 6.00, As Taught in Fall 2008: Here is a theorem below:

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.

Using the theorem above, write an exhaustive search to find the largest number of McNuggets that cannot be bought in exact quantity, i.e. write an iterative program that finds the largest number of McNuggets that cannot be bought in exact quantity. Format of search should follow the outline below:

Hypothesise possible instances of numbers of McNuggets that cannot be purchased exactly, starting with 1. For each possible instance, called n, test if there exists non-negative integers a, b, and c, such that 6a+9b+20c = n. If n McNuggets cannot be bought in exact quantity, save n. When have found 6 consecutive values of n where 6a+9b+20c = n, the last answer that was saved (not the last value of n that had a solution) is the correct answer, since from the theorem, any amount larger than this saved value of n can also be bought in exact quantity

The error is in line 14 of the code below and this is the error:

elif(6*a + 9*b + 20*c < n_saved or 6*a + 9*b + 20*c > n_saved):
    ^
SyntaxError: invalid syntax

Here is the code:

def largest_not(a, b, c, n, n_saved):
    a = 0
    b = 0
    c = 0
    n = 0
    n_saved = 0
    for a in range (10):
        for b in range (10):
            for c in range (10):
                for n in range (10):
                    for n_saved in range (10):
                        if (6*a + 9*b + 20*c == n):
                            print (n)
    elif(6*a + 9*b + 20*c < n_saved or 6*a + 9*b + 20*c > n_saved):
        print (n_saved)
    if (n - n_saved > 5):
        print "Largest number of McNuggets that cannot be bought in exact quantity: " + "<" + n_saved + ">"
    else :
        print "Have not found the largest number of McNuggets that cannot be bought in exact quantity."

a=6
b=9
c=20
largest_not(a, b, c, n, n_saved)

Answer 1

Here is a way to solve this:

def check(n):
    """check if n nuggets can be bought exactly with packs of 6, 9 and 20"""
    for a in range(20):
        for b in range(20):
            for c in range(20):
                if (6*a+9*b+20*c==n):
                    return True
    return False


### look for a serie of 6 successives n
### to apply the theorem
nb_i  = 0   ## number of successive good n found
sv_i  = 0   ## last good n found
bad_i = 0   ## last bad n found


for i in range(1, 100):
    if (check(i)):
        nb_i+=1
        sv_i=i
    else:
        bad_i=i
        nb_i=0
        sv_i=0
    if nb_i==6:
        print "Solved: the biggest number of nuggets you cannot buy exactly is: " + bad_i
        break

result is:

Solved: the biggest number of nuggets you cannot buy exactly is:  43

Answer 2

Your elif needs to be inline with your if. However, your algorithm will also not work.

I got 43 as the largest number not possible: I'm sure this solution could be optimised.

def check(n):
    # a in [0..max times 6 goes into n]
    for a in range(0, n // 6 + 1):     
        # b in [0..max times 9 goes into remainder]   
        for b in range((n - 6*a) // 9 + 1):           
            # c in [0..max times 20 goes into remainder]    
            for c in range(0, (n - 6*a - 9*b) // 20 + 1):
                if 6*a + 9*b + 20*c == n:
                    return (a, b, c)
    return None

def largest_not():    
    n = 1
    last_n_not_possible = 1
    while (n - last_n_not_possible <= 6):        
        can_purchase = check(n)
        if can_purchase is not None:
            print("Can purchase ", n, ' = ', can_purchase[0],'*6 + ', can_purchase[1],'*9 + ', can_purchase[2], '*20', sep='')
        else:
            print("Can't purchase", n)
            last_n_not_possible = n
        n = n + 1

    return last_n_not_possible

print("Answer: ", largest_not())