Problem solving - sum of products

I did this on the last day, way too busy for other courses.

I chose this question, "If n represents a positive whole number, what is the largest product that can be formed by multiplying the elements of a list of positive whole numbers that sum to n?" because it is very interesting, plus I like to play around with numbers a lot. Anyways, onwards to the proof:

1. Understand the problem:

This question basically asks a formula for the largest product made up of numbers that sums up to any number n.

2. Devising a plan:

Many ways to do this:

brute force - trying out a large number of values, find a pattern and test it out with extremely large number to confirm the formula. It's a good way to check your own intuition but not very efficient (especially if your guess is wrong).

equations - there's got to be some ways of relating sum and products as an equation, certainly this way is fast and more efficient as it is already mathematically rigorous and straightforward.

working backward - It may work with other problems, but may not work with this one. Basically use a random number, find the most numbers you can that makes up the two largest multiplier.

I choose a combination of brute force (this problem is relatively small), and equations (to express the formula).

3. Carrying out the plan:

The first few natural numbers are not interesting, the pattern starts to make sense with n >= 6.

number 6

list of possible sums (1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 2), (1, 1, 1, 3), (1, 1, 4), (1, 5), (2, 2, 2), (1, 2, 3), (3, 3)

biggest product 9

number 7

list of possible sums (1, 1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 2), (1, 1, 1, 1, 3), (1, 1, 1, 4), (1, 1, 5), (1, 6), (1, 2, 2, 2), (1, 1, 2, 3), (1, 3, 3), (2, 2, 3)

biggest product 12

number 8

list of possible sums (1, 1, 1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 1, 2), (1, 1, 1, 1, 1, 3), (1, 1, 1, 1, 4), (1, 1, 1, 5), (1, 1, 6), (1, 7), (2, 2, 2, 2), (2, 3, 3), (1, 2, 2, 3), (1, 1, 3, 3)

biggest product 18

... and so on.

Next, onwards to the formula, from the pattern above the biggest product from the list of sums is a combination of 2s, and 3s.

Given a number n, breaks the number into two-halves and find all possibles factor of floor(n/2) and ceil(n/2) (in case n is odd) those two halves represented with 2s and 3s, with 3s the most priority (i.e. a number 8 can be made by 2 X 2 X 2 X 2, but it's value is the biggest for 3 X 3 X 2).

If n is even, let k = n - 3m, where k <= n mod 3, with m \in N. Then either k is 0 or even, thus k can then be represented as powers of 2 (i.e. k = 2^p, for p \in N). Therefore n = 3m or n = 3m + 2^p, for m, p \in N, that will represent the biggest product by multiplying p 2s and m 3s (i.e. 8 = 3 X 2 + 2^1, and product = 2 X 3 X 3 = 18).

Similar case for n = odd. Then it will be of three cases: if it equals 0 after mod 3, then it is a multiples of 3, say, 3m, for m \in N. If it equals 1 after mod 3, then the equation becomes (let t be the odd half) t = 3^(s-1) + 2r, with r, s \in N, where s is the biggest powers of 3 t can obtain). If it equals 2 after mod 3, then t = 3^s + 2r, s, r \in N, since the remainder of mod 3 is a multiples of 2. Then the biggest product can be obtained by multiplying s 3s and r 2s.

So n = 3m or 3m + 2^p or 3^(s-1) + 2r or 3^(s) + 2r, depending on the situation. The biggest product is then the multiples of m or s times of 3s and p or r times of 2s.

4. Looking back:

I'm done the proof, but the mathematical expression can be simplified greatly, I need more knowledge in order to do so.

The combination works greatly because brute force allows me to find a pattern, while using equations allows me to reduce the amount of explanation I need to write/type (it's still a lot to explain the cases).

My solution may not be the neatest, but I think it works perfectly with all n. However I believe there are other equations that are shorter and much more elegant, my skill of proving is not up to that level yet...