Cheap and Secure Web Hosting Provider : See Now

Finding three factors of a number with minimal sum

, ,
Problem Detail:

Suppose that we have a number $x \in \mathbb{Z}^+$.

I am seeking an algorithm to find three numbers $a, b, c \in \mathbb{Z}^+$ such that $a \times b \times c = x$ and $a + b + c$ is minimum.

Is this problem a variant of subset sum? Am I stuck with an exponential time algorithm?

Examples

$32 = 4 \times 4 \times 2$
$36 = 4 \times 3 \times 3$
$11 = 11 \times 1 \times 1$
$6 = 2 \times 3 \times 1$

Answered By : Tom van der Zanden

The problem does not require exponential time. It can be solved in subexponential, but superpolynomial time.

The first step is to find the prime factorization of $x$, which can be done with the general number field sieve.

Next, enumerate all possible values of $a,b$ and for each tuple $(a,b)$ compute $c$ to find the triple with the minumum sum. A number $x$ has at most $\exp(O(\log x / \log \log x))$ divisors, so there are also at most $\exp(O(\log x / \log \log x))$ such tuples.