Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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. –  Craig Sep 19 '11 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. –  Craig Sep 19 '11 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. –  Michael Lugo Sep 19 '11 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!$. –  Michael Lugo Sep 20 '11 at 0:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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