1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Need more clarification: whether $x, y \in \mathbb{R}$ or $\mathbb{C}$. $\endgroup$
    – Neeraj
    Jun 2, 2012 at 7:38
  • $\begingroup$ x, y are inegers $\endgroup$
    – Sahil
    Jun 2, 2012 at 8:03
  • $\begingroup$ 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}$. $\endgroup$
    – Tony Huynh
    Jun 2, 2012 at 8:52
  • $\begingroup$ 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. $\endgroup$
    – Goldstern
    Jun 2, 2012 at 9:21
  • $\begingroup$ I agree with Goldstern, $c$ should not be very lagre. $\endgroup$
    – Neeraj
    Jun 2, 2012 at 9:31

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 2, 2012 at 15:51
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.