# find the minimum difference between the factors of a number

Given a number c, what is the smartest way to find |x - y| such that x * y =c and |x - y| is minimum

• Need more clarification: whether $x, y \in \mathbb{R}$ or $\mathbb{C}$. – Neeraj Jun 2 '12 at 7:38
• x, y are inegers – Sahil Jun 2 '12 at 8:03
• I don't think this is smart enough, but one approach is to make a sorted list of the divisors of $c$ (see velocityreviews.com/forums/…) and then do a binary search for the divisor that is closest to $\sqrt{c}$. – Tony Huynh Jun 2 '12 at 8:52
• What does "smart" mean? How large are your numbers? If $c$ is very large, then no smart (i.e., fast) way of finding nontrivial $x,y$ with $x*y=c$ is known. – Goldstern Jun 2 '12 at 9:21
• I agree with Goldstern, $c$ should not be very lagre. – Neeraj Jun 2 '12 at 9:31

As @Goldstern commented, if you don't have the factorization of $c$, then in general you can't even necessarily find non-trivial factors.

Even assuming you're given the full prime factorization of $c$ this looks like an optimization version of the partition problem, so I think an exact solution will still be hard in the most general case.

Write $c=\prod p_i$ as a product of primes (allowing repetitions), then your question is finding a partion of the multiset $S=\{\log p_i\}$ into $S1$ and $S2$ so that $|\exp(\sum_{S1})-\exp(\sum_{S2})|$ is minimized. Since $\sum_{S1}+\sum_{S2}$ is fixed, this also corresponds to the minimum of $|\sum_{S1}-\sum_{S2}|$.

While the problem is usually posed as a discrete one, I expect that some of the algorithms referenced on Wikipedia can be applied effectively.

• And conversely, given a hard instance $S \subset {\bf R}^{> 0}$ of the partition problem, one can find $C>0$ and primes close enough to $\exp C\cdot S$ that their product is a hard instance of the nearest-factor problem at hand. – Noam D. Elkies Jun 2 '12 at 15:51

I will suggest the following:

First, assume $x,y \in \mathbb{R}$, as the line $y=x$ and the hyperbola $y=\frac{c}{x}$ intersect, denote the intersection coordinate as $(x_0,y_o)$. If $(x_0,y_o)$ is an integer coordinate, then $|x_0-y_0|=0$ is the minimum.

If $(x_0,y_o)$ is not an integer coordinate. then consider the $x$-coordinate of $x_0$, say $[x_0]$ and $\lceil x_0 \rceil$, the greatest and least integer respectively. Now look for the $y$-coordinate $\frac{c}{[x_0]}$ and $\frac{c}{\lceil x_0 \rceil}$, If any of these $y$-coordinates is an integer, then just take the difference $|x_0-\frac{c}{[x_0]}|$ or $|x_0-\frac{c}{\lceil x_0 \rceil}|$ , one has the desired result, If none $\frac{c}{[x_0]}$ and $\frac{c}{\lceil x_0 \rceil}$ are integer, then like before repeat the process, this time consider $x$-corodinates $[x_0]-1$ and $\lceil x_0 \rceil +1$ and proceed similarly. Once one knows $c$ before, then it is easy to proceed.

The main thing is one has to know divisors of $c$ to make the above process, quick. Also $c$ has to be small integer, else, there is no smart or easy way.