Post Three

Products of Sums

1) Understanding the problem

What is the problem at hand? Given n, a positive integer, find the list, whose sum is n, with the largest product.

Some sample data:

n	Lists	P
1	[1]	1
2	[1,1], [2]	2
3	[1,1,1], [1,2], [3]	3
4	[1,1,1,1], [1,1,2], [2,2], [3,1], [4]	4
5	[1,1,1,1,1], [2,2,1], [3,2]...	6
6	[1,1,1,1,1,1], [2,2,2], [4,2], [3,2,1], [3,3]...	9
7	[1,1,1,1,1,1,1], [2,2,2,1], [4,2,1], [3,3,1], [3,2,2], [3,4]...	12
8	[1,1,1,1,1,1,1,1], [2,2,2,2], [4,4], [3,3,2]...	16
9	[1,1,1,1,1,1,1,1,1], [2,2,2,2,1], [4,4,1], [3,2,2,2], [3,4,2], [3,3,3]...	27

(I found some more lists for higher n values but this is enough to see what's happening)

One thing that we need to strive for here is to process this data into a general form in order to satisfy the problem at hand easily given any integer n.

2) Devising a plan

So, where do we go from here? Well we have all this data, we might as well put it to use. From what I could gather the commonality between the lists with the largest product is that they are all made up of, exclusively, the numbers 2, 3 and 4. But since 2+2=4 and 2*2=4 we can reduce the 4's and say the lists are all made up of 2 and 3. We also note that 3's seem to be the optimal choice as long as choosing a 3 does not mean a 1 will be in the list.

Our plan then is to generalize and see just how much 3's we can get out of some number n without having a remainder of 1.

3) Carry out the plan

We can look at the remainder of dividing some number by 3 and approach this on a case by case basis.

1. n % 3 = 0
2. n % 3 = 1
3. n % 3 = 2

1. The list is made up of n/3 threes.
2. The list is made up of (n-4)/3 threes and 1 four (or 2 twos)
   This is because when n % 3 = 1 then (n-4) % 3 = 0. We add 4 to the list to compensate for subtracting. This method allows us to get the most 3's out of n without having a 1 in the final list.
3. The list is made up of floor(n/3) threes along with the remainder, 1 two.

So given some integer n we can easily find the list we want by following these three cases.