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

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

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

$\endgroup$
  • $\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$ – Albert Hendriks Dec 19 '17 at 22:25
0
$\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, privacy policy and cookie policy

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