# Maximizing product of list of integers whose sum equals n

Given a positive integer n, find the list of positive integers whose product is the largest among all the list whose sum is n. For example, if n is 4 the desired list is 2,2 because 2x2 = 4 is larger than 1x1x1x1 = 1, 2x1x1 = 2 and 3x1 = 3, if n is 5, the desired list is 2, 3.

what is the desired list if n = 2001;

Actually is an algorithm to generate this list. After tried lots of example, i discern(hope am right) for n > 5 its a list of 3's, and a remainder n % 3;

so for n = 2001, I got a list of 667 3's.

Question.

If Correct, What property of 3 makes it the ideal integer in that it composes (mostly) this list?.

• Highly recommend searching OEIS for common integer sequences like this: oeis.org/A000792 – ryan Jul 22 '17 at 0:54

Intuitively the function $(n/x)^x$ is maximized at $x=\frac{n}{e}$ and 3 is closest to $e$.
The property that makes 3 special in this case is that it can only be decomposed into sums whose products are smaller than 3. That is, $3\cdot0 = 0$, and $2\cdot1=2$.
Think of it like this. Given a list of integers $[x_1, x_2, ..., x_n]$ that sum up to the desired $y$, we have the product $x_1 \cdot x_2, \cdot ...\cdot x_n$ (obviously). For each $x_i$ if there is a a set of integers $j,k,l,...$ with $x_i = j + k + l + ...$ such that $x_i < j \cdot k \cdot l \cdot ...$ then we can replace $x_i$ in the original list with $j,k,l,...$ and increase the product. The numbers that can't be decomposed, 2 and 3, will makeup the final list. The trick for optimizing is the choice of $j,k,l,...$.