The Product of Sums

During the previous class, we had another opportunity to give our minds a swing at problem solving. This time we had to devise the maximum product that can be formed from a list of numbers. These list of numbers summed up to a positive integer. After some consideration, I came to the conclusion that the best combination of numbers to use in the list, in order to achieve the max product was 2 and 3. The only explanation I have at this point for why this works is that it does for the smaller cases of n. Since it works for these smaller cases i.e. 5-10, therefore it must hold for the larger cases, since the larger cases are merely a combination of smaller ones. At least that's the theory. And being a CSC student, it made sense for me to code it up! And this is what I came up with:

def prod_sum(n):
    prod = 1
    L = []

    while n > 1:
        if n == 4 or n == 2:
            L.append(2)
            n -= 2
        elif n >= 3:
            L.append(3)
            n -= 3

    for x in L:
        prod *= x
    return prod


Its not by any means the most elegant solution, but it seems to work. Recursion might be a better way to attack it, but late Thursday night isn't a good time for recursion...