3
$\begingroup$

Given positive integers $m<n\in\mathbb{N}$ is there an algorithm to find integers $z_1, z_2\in \mathbb{Z}\setminus\{0\}$ such that $\frac{m}{n}$ is best approximated by $\frac{1}{z_1}+\frac{1}{z_2}$? (In other words, the goal is to minimize $|\frac{m}{n}- (\frac{1}{z_1}+\frac{1}{z_2})|$.)

$\endgroup$
5
  • $\begingroup$ Why would you look for an approximation like that? Few rational numbers have good approximations of that form. For example, you can't approximate $5$ very well like that. Anyway, there is an obvious algorithm starting with the larger piece, which can't be much smaller than $\frac{m}{2n}$ unless it is $1$, checking for the best smaller piece. Is this algorithm unsatisfactory? $\endgroup$ Sep 2, 2014 at 13:20
  • $\begingroup$ Are approximations of the form $(1/z_1) - (1/z_2)$ also allowed, as the question title seems to indicate? $\endgroup$ Sep 2, 2014 at 13:47
  • $\begingroup$ The solution to the best approximation problem may not be unique. $5/6 = 1/2 + 1/3 = 1/1 - 1/6$. But in any case, the search space is finite if you only want an algorithm. For the "addition" problem, let $w$ be the natural number such that $1/w$ is the largest one less than $m/n$. Then clearly $z_1 \in \{w, \ldots, 2w - 1\}$. For each candidate $z_1$ just compute the ceiling and floor of $1 / (m/n - 1/z_1)$ and find the best. A similar search algorithm can be given for the case where $z_1> 0$ and $z_2 < 0$. (The search space has size $O(n/m)$, btw.) $\endgroup$ Sep 2, 2014 at 14:10
  • $\begingroup$ @OwenBiesel Yes, because $z_1, z_2$ are (positive or negative) integers. $\endgroup$ Sep 2, 2014 at 14:39
  • $\begingroup$ See also mathoverflow.net/questions/179574/… from the same source. $\endgroup$ Sep 2, 2014 at 23:26

1 Answer 1

3
$\begingroup$

The comments above give a good search algorithm. I wanted to note that the answer can depend very delicately on the exact value. If $\frac{m}{n}=\frac{1}{x}+\frac{1}{y}$ then also $\frac{m}{kn}=\frac{1}{kx}+\frac{1}{ky}$ this allows multiple solutions in some cases. For example all $11$ of these pairs give $\frac{5}{84}:$

$$[7,-12],[12,-42],[14,-84],[15-140],[16,-336],$$$$[17,1428],[18,252],[20,105],[21,84],[24,56],[28,42]$$

For rational (or real) values $r$ close to $\frac{5}{84} \approx 0.059524$ the best approximation (if unique) is likely to come from $[x,y]$ with $5 \le x \le 30$ but small changes in $r$ can cause $x$ to vary up and down.

$\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.