0
$\begingroup$

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?.

$\endgroup$
1
  • $\begingroup$ Highly recommend searching OEIS for common integer sequences like this: oeis.org/A000792 $\endgroup$
    – ryan
    Commented Jul 22, 2017 at 0:54

2 Answers 2

6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ +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. $\endgroup$ Commented Dec 19, 2017 at 22:25
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.