Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers 2

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.

share|improve this answer
2  
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
add comment

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.

share|improve this answer
add comment

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.