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})|$.)
$\begingroup$
$\endgroup$
5
asked Sep 2, 2014 at 13:02
-
$\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$– Douglas ZareCommented 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$– Owen BieselCommented 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$– Willie WongCommented Sep 2, 2014 at 14:10
-
$\begingroup$ @OwenBiesel Yes, because $z_1, z_2$ are (positive or negative) integers. $\endgroup$– Dominic van der ZypenCommented Sep 2, 2014 at 14:39
-
$\begingroup$ See also mathoverflow.net/questions/179574/… from the same source. $\endgroup$– Gerry MyersonCommented Sep 2, 2014 at 23:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Sep 3, 2014 at 7:55