# If the product of $x$ positive integers is $n!$ What is the smallest possible value their sum can have?

If the product of $x$ positive integers is $n!$ What is the smallest possible value their sum can have?

I was wondering what could be the most efficient strategy to solve this problem for sufficiently small values of $x$ and $n$.

For example, if $x=4$ and $n = 10$,the smallest sum would be that of $40,45,48,42$ such that $$40 \times 45 \times 48 \times 42 = 10!$$ and hence that required answer is $$40+45+48+42=175$$However,I used pure brute-force approach to get this result,I am inquisitive about a general strategy for this problem.

• Have you tried Lagrange multipliers? Sep 19, 2011 at 18:45
• @DJC:I have just started taking my multivariable calculus lessons,we haven't yet reached there. Sep 19, 2011 at 18:48
• @Srivatsan Narayanan:Both $x$ and $n$ are inputs. Sep 19, 2011 at 19:04
• Nice problem. Exact answers are probably hopeless, but good bounds should be possible because of insensitivity near the minimum. Sep 19, 2011 at 19:32
• Also, a quick proof that the particular set you gave is the best possible: to minimize $x+y+z+w$ subject to the constraint $xyzw=C$, you take $x=y=z=w=C^{1/4}$. (Use Lagrange multipliers if you've seen them; in any case this should seem reasonable.) So you can't do better than a sum of $4(10!)^{1/4} \approx 174.6$; in fact $40+42+45+48 = 175$. Sep 19, 2011 at 23:49

The likely idea is that you would still take the prime factorization of $n!$, and then try to group the primes into $x$ different stacks that all have as close to the same product as possible.
• This is a knapsack-ish problem -- the values you are trying to fit into the $x$ boxes are the logs of the primes. In regards to this, the large primes are not as much of a problem as you might think; greedy algorithms tend to work well. And since you have large numbers of small primes (2 shows up ~n times in n!), you have a fair amount of "filler" to even things out. Sep 19, 2011 at 20:25
• To be specific, I am suggesting a greedy algorithm where you run thru the primes in order of decreasing size, each time multiplying the smallest of your $x$ numbers by said prime. Sep 19, 2011 at 20:39
• Another potential greedy algorithm: if we want to write $n$ as a product of $d$ factors, start by taking the factor of $n$ which is closest to (or closest to but above, or closest to but below) $n^{1/d}$; then write $n$ divided by that factor as a product of $d-1$ factors in the same way. Sep 19, 2011 at 23:53
• However, the algorithm I gave in my previous comment does not always give the optimal solution. Consider writing $14!$ as a product of four factors. $14!^{1/4} = 543.378$; the smallest factor of $14!$ greater than $543$ is $550$; the smallest factor of $14!/550$ greater than $(14!/550)^{1/3}$ is $567$; the smallest factor of $14!/(550\times567)$ greater than its square root is $546$. We get $550 + 567 + 546 + 512 = 2175$. But $560+540+546+528 = 2174$, and both sets multiply to $14!$. Sep 20, 2011 at 0:06