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.

Given a number $N$ I would like to factor it as $N=ab$ where $a$ and $b$ are as close as possible; say when $|b-a|$ is minimal. For certain $N$ this is trivial: when $N$ is prime, a product of two primes, a perfect square, or one less than a perfect square, for example.

But in general it seems tricky. A lot of obvious first steps don't work. For example, it is tempting to guess that when $N=k^2M$, we can find $a_M\cdot b_M = M$, and the optimal solution for $N$ will be $ka_M\cdot kb_M$. But this is quite wrong; a counterexample is $N=20$. Are there any divide-and-conquer tactics of this sort that do work?

An obvious algorithm to find the optimal $a$ and $b$ might begin by calculating $s=\left\lfloor\sqrt N\right\rfloor$, which can be done efficiently, and then by working its way down from $s$ looking for a factor of $N$ by trial division, which is slow. Is there a more efficient algorithm?

It seems to me that even if the complete factorization of $N$ is known, partitioning the factors into two sets whose products are as close as possible will be NP-complete; it looks similar to the subset-sum problem, for example.

share|improve this question
    
By close, I assume $\vert b - a \vert$ is minimized? –  user17762 Jan 19 '13 at 3:47
    
I was not sure whether to minimize $|b-a|$ or $\left|\log \frac ba\right|$. But I think the same factorizations are optimal regardless of which metric one chooses. I have amended the question to commit to minimizing $|b-a|$. –  MJD Jan 19 '13 at 3:49
    
Peripheral comment: I think I first began to consider this problem when I noticed that $7! = 70\cdot72$. –  MJD Jan 19 '13 at 3:54
1  
Varients of Fermat's factorization method would be more efficient then your algorithm –  Ethan Jan 19 '13 at 3:54
1  
Because of the monotonicity of the log function, minimizing $|b-a|$ or $|\log \frac ba| =| \log b - \log a| amount to the same thing. –  Ross Millikan Jan 19 '13 at 3:57

3 Answers 3

You are right it is the knapsack problem. If you factor $N=\prod_i p_i^{a_i}$ and take the log, you get $\log N = \sum_i a_i \log p_i$. Now you are looking to fill a knapsack of size $\frac 12 \log N$ as full as possible with things of size $\log p_i$ (and a limit of the quantity of each) without going over.

share|improve this answer

There are some modest improvements one can make over trial division, at least when $N$ is odd. Certainly not enough to make this competitive with modern factoring methods and knapsack algorithms in most cases, but still better than trial division.

See the sections "Fermat's and trial division" and "Sieve improvement" in the Wikipedia article on Fermat factorization; in the case of odd $N$, $N = ab$ with $a$ and $b$ close together is equivalent to $N=A^2 -B^2$ with $B$ as small as possible.

share|improve this answer

This is a hard problem in general since factoring is already a hard problem. Though perhaps you are assuming that $N$'s factorization is already known? It seems not, since you give an algorithm that does not use its factorization.

Given $N=p_1^{a_1}p_2^{a^2}\cdots p_k^{a^k}$ where the $p_i$ are prime, you want to partition this multiset into multisets $S$ and $T$ such that their respective products are as close as possible. I'm going to guess this is NP-Hard since it's pretty similar to the knapsack problem (http://en.wikipedia.org/wiki/Knapsack_problem)

share|improve this answer
1  
Factoring isn't known to be hard. The hardness comes from the knapsack property. –  John Moeller Jan 19 '13 at 4:05
    
Factoring is thought to be hard. Knapsack is NP-Hard, and therefore thought to be hard. If $P = NP$ then all of these are poly-time solvable, but that's unlikely. The best known general factoring algorithms are super-polynomial (on a conventional computer; quantum algorithms are polynomial-time). –  Fixee Jan 19 '13 at 4:19
1  
Factoring is actually thought not to be NP-hard: en.wikipedia.org/wiki/… –  John Moeller Jan 19 '13 at 4:22
    
Correct, which is why I was careful to not claim that it was. If you know an efficient (meaning poly-time) factoring algorithm, please send me a private note and we'll write a paper. Or start a company. Or be captured/assassinated before we can do either... –  Fixee Jan 19 '13 at 4:35
1  
There's no need to be snide. My point here is that if you mention "hard" in the context of complexity it's good to be specific about what you mean and avoid the colloquial use of "hard" as something that's merely practically intractable. There are problems in $P$ that are practically "hard." –  John Moeller Jan 19 '13 at 4:41

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.