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