Minimum sum among fixed length factors of a number

Question

I think this question is famous, but I searched a lot in the internet with many keywords and unfortunately I did not find any related problem. I will appreciate any helpful answers and any guidance for similar questions and problems.

Suppose the integers $n$ and $k$ are given and the set $S$ shows all possible factorization of the integer $n$ into $k$ factors. The factors of these factorization not necessarily primes and can be composite. Also, at most one factor can be the number $1$. For example, if $n=128$ and $k=3$, we have:

$S=\lbrace 2\times4\times16, 4\times4\times8, 2\times 2\times32, 1\times2\times64, 1\times4\times32,1\times8\times16\rbrace$.

For fixed numbers $n$ and $k$ (and also the set $S$), let $m\in S$ and $m=l_1\times l_2 \ldots\times l_k$. We define $S(m)=\sum_{i=1}^k{l_i}$.

What can we say about the minimum of $S(m)$, where $m$ changes in the set $S$? Do we have any formula for finding this minimum respect to the $n$ and $k$?

For the above example, the minimum is happen for $m=4\times4\times8$ and $S(m)=16$.

Is this a famous problem and are there any works related to this problem?

$Note:$ It can be seen that if the factors of $m\in S$ be as much possible as close to each other, then the sum of its factors converges to the minimum.

Answer 1

At the end are a few interesting numerical examples. Here is a general discussion:

This is not a very well specified question. The answer depends strongly on the prime factorization of $n$. Very easy cases include $n$ prime and $n$ a perfect $k$th power. $n$ a prime power is easy too. If the number of distinct prime factors is "small" it might also be fairly easy. Let's consider two stages (then ignore the first) 1) Find the prime factorization of $n$ obtaining a list $P$ of primes. 2) Given a list $P$ of integers (which happen to be prime) partition it into $k$ sublists $P_1,\cdots,P_k$ with roughly equal products; specifically, minimize $\sum_i\prod_{p \in P_i}p$. It could be as satisfying to you to minimize $\max_i\prod_{p \in P_i}p.$ That might be easier to work with. It does allow us to replace the nubers in $P$ by their logarithms and minimize $\max_i\sum_{p \in P_i}\log{p}.$ That transforms it into the multiprocessor scheduling problem (The closely related bin packing problem would be more appropriate to the question of how many factors are needed if none can be larger than a given size $v$.)

Step 1) can (as commented in another answer) be very difficult. To get the absolute best answer for step 2) , even in the case $k=2$, might be NP-hard (I will argue.) However, a greedy algorithm will, I suspect, easily get answers under $(\frac{OPT}{k})^{4/3}$ where $OPT$ is the optimal value. It is suspected that step 1) is not NP-hard, however we can't even get started until we know the prime factorization. When we do get to step 2, the fact that the integers are prime is probably not relevant to the solution or bounds, it just makes examples a little harder to give. But if we wanted to use a list $P$ with integers $6,10,15$ repeated various numbers of times each, we could instead use the primes $6,000,011$ along with $10,000,019$ and $15,000,017$ and probably have about the same ordering on the possibilities.

I will assume that the prime factorization is already known and reframe the question as: "How can we get from the prime factorization to a "good" factorization?" Here is a simple procedure which I suspect is at worst $(OPT/k)^{4/3}$ where the optimal value is $OPT$: Start with $l_1=l_2=\cdots=l_k=1$ then run through the prime factors in order of decreasing size and given a prime factor $p$, replace $l_i$ by $pl_i$ where $l_i$ is minimal among the current $k$ values.

I base by suspicion on analogy to the multiprocessor scheduling problem. That problem is: Given an integer $k$ and list $J$ of integers, partition $J$ into $k$ sublists $J_1,\cdots,J_k$ so as to minimize $\max_i\sum_{j \in J_i}j.$ Then the procedure is at worst $4/3-1/3k$ times the optimal (there are other procedures which do better with a more sophisticated strategy). The analogy would be stronger if the criteria for our problem was to minimize $\max_i l_i,$ but the minima seem likely to be at about the same place. At least for $k=2$ they are exactly at the same place.

Examples:

The greedy procedure for multiprocessor scheduling has a bad example $J=[5,5,4,4,3,3,3]$ which it partitions as $[5,3],[5,3],[4,4,3]$ with $4+4+3=11$ not as good as $5+4=9$ from $[5,4],[5,4],[3,3,3].$ For our problem this would become $n=p^3q^2r^2$ with $p,q,r \approx b^3,b^4,b^5$ for some base $b.$ Using $b=10$ and $p,q,r=1009, 10007, 100003$ we have $qr+qr+p^3 \approx 3\cdot 10^9$ which is better than the greedy $pr+pr+pq^2 \approx 1.01\cdot10^{11}$

This example shows that minimizing the sum and minimizing the maximum can give significantly different answers. Consider the primes $p=101,q=601,r=90001.$ Then for $n=p^2q^3r^3$ the factorization $[q^2,p^2r,r^2]\approx [2.2\cdot10^8,9.2 \cdot 10^8, 8.1 \cdot 10^9]$ has $q^2+p^2r+r^2 \approx 1.3\cdot 10^9$ while the factorization $[pr,pqr,pqr]\approx[5.4 \cdot 10^7,5.5 \cdot 10^9,5.5 \cdot 10^9]$ has $pr+pqr+pqr \approx 1.6 \cdot 10^9$. Using the prime $r=pq+2=60703$ would make the ratio of the sums about $1.6$ although then the maximum entries would be closer. In general, if $q \approx ap$ and $r \gt pq$ (but not by too much) with $p$ much larger than $a$, then $\frac{q^2+p^2r+r^2}{pr+pqr+pqr} \approx \frac{2a}{a+1}.$

Answer 2

Given integers $n$ and $k$, asking for a `formula' for the smallest sum of $k$ integers whose product is $n$ is certainly not appropriate. Rather one should ask for an algorithm. -- And the main task such an algorithm needs to perform is to find the prime factorization of $n$. In case the prime factors of $n$ are large, that is really difficult, and there are no polynomial-time algorithms known for this. The asymptotically fastest known integer factorization algorithm is the general number field sieve (cf. http://en.wikipedia.org/wiki/General_number_field_sieve). Once you know the factorization, the rest is straightforward and almost no work.