# 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, what is an algorithm to generate this list? After tried lots of examples, I discern (hope am right) for n > 5 it's 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, 2017 at 0:54

Intuitively the function $(n/x)^x$ is maximized at $x=\frac{n}{e}$ and 3 is closest to $e$.

• +1, but beware that 3 is coincidentally closest to e is strictly not the reason that 3 is better than 2. It should be something like "3 is closest to e on a logarithmic scale". I think. Dec 19, 2017 at 22:25

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,...$.