products of sum problem

Hey again!

towards the beginning of the term we were introduced to George Polya's method to approaching problems presented in "How to solve it". I intend to follow this method to try to reach a solution to a problem that was presented to us in class.

• Understand the problem:

we are trying to find the maximum product that can be formed of a list of positive integers that sum up to n where n is a positive integer and if we can generalize the solution, we can write a function in python that returns the biggest product of n.

• Plan a solution:

I think the easiest way to tackle this problem is to actually write down all possible lists that sum up to a particular integer and then try to find the biggest product. And if we do this process to enough integers, hopefully, we will recognize a pattern that will help us to reach the solution.

• Carry out the plan:

First: 

we need to write down all the possible lists of positive integers of n for n = 1 till n=6 and determine the largest product for each. 

The best way to write all lists is to start splitting up n into 1s and then gradually group them together to form all possible lists, keeping track at the same time of the product produced by each list (product of elements in the list). and then finding the max of all these products.

Here is the possible lists for n in the interval [1,6]:

                                 

 

1-> 1	(1)=1
2 -> 2	(1,1) = 1	(2) =2
3 -> 3	(1,1,1)=1	(3)=3
	(2,1) =2
4-> 4	(1,1,1,1) =1	(4)=4
	(1,1,2) = 2	(2,2)=4
	(1,3)=3
5->6	(1,1,1,1,1)=1	(5)=5
	(1,1,1,2)=2	(3,2)=6
	(1,1,3)=3
	(1,4)=4
6->9	(1,1,1,1,1,1)=1	(6)=6
	(1,1,1,1,2)=2	(2,2,2)=8
	(1,1,1,3)=3	(1,2,3)=6	(3,3)=9
	(1,1,4)=4	(2,4)=8
	(1,5)=5

Second:

we can observe the following:

- lists that include 1 as an element are not the ones with the biggest sum (except for 1, of course).

- grouping n into 3s and 2s produce the largest product.
However, as you might expect having more 3s would increase the product than having more 2s.

Third:

now we can write a python function that groups n into 3s when possible or 2s.
I used recursion for that: