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.

  • $\begingroup$ Have you tried Lagrange multipliers? $\endgroup$
    – JavaMan
    Sep 19, 2011 at 18:45
  • $\begingroup$ @DJC:I have just started taking my multivariable calculus lessons,we haven't yet reached there. $\endgroup$
    – Quixotic
    Sep 19, 2011 at 18:48
  • 2
    $\begingroup$ @Srivatsan Narayanan:Both $x$ and $n$ are inputs. $\endgroup$
    – Quixotic
    Sep 19, 2011 at 19:04
  • 5
    $\begingroup$ Nice problem. Exact answers are probably hopeless, but good bounds should be possible because of insensitivity near the minimum. $\endgroup$ Sep 19, 2011 at 19:32
  • 3
    $\begingroup$ 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$. $\endgroup$ Sep 19, 2011 at 23:49

1 Answer 1


Well, the general idea is maybe not so bad. Just as a d-dimensional cube has the minimal surface area for a given volume of d-dimensional parallelopipeds (rectangular d-prisms in particular), we would want our numbers to be as close in value as possible.

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.

One might ask: how does one go about finding out which primes are in which stacks? That's a great question. It sounds to me to be roughly as computationally challenging as the knapsack problem (e.g. wiki), which is NP-complete. But that might not be true. The advantage is that factorials behave sort of nicely, so 'most' factors should be able to be divided fairly equally for large n, low x. It's the few 'large' primes in the factorization that can mess everything up.

But at least this gives the brute forcing a direction of attack. This started as a comment but grew to an incomplete answer. But I'll think more on it and see what comes up.

  • $\begingroup$ 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. $\endgroup$
    – Craig
    Sep 19, 2011 at 20:25
  • $\begingroup$ 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. $\endgroup$
    – Craig
    Sep 19, 2011 at 20:39
  • $\begingroup$ 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. $\endgroup$ Sep 19, 2011 at 23:53
  • $\begingroup$ 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!$. $\endgroup$ Sep 20, 2011 at 0:06

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.