2
$\begingroup$

Let $U =\{\frac{1}{n}: n\in \mathbb{N}\} \cup \{-\frac{1}{n}: n\in \mathbb{N}\}$ be the set of positive or negative unit fractions.

Given positive integers $m<n \in\mathbb{N}$, how do you find $u_1, u_2 \in U$ such that $|\frac{m}{n} - (u_1+u_2)|$ becomes minimal?

A weaker problem would be the following: Given positive integers $m<n \in\mathbb{N}$ and a positive integer $k\in\mathbb{N}$ devise an algorithm that outputs "Yes" if there exist $u_1, u_2\in U$ such that $|\frac{m}{n} - (u_1+u_2)| < \frac{1}{k}$, and "No" otherwise.

|cite|improve this question
$\endgroup$
  • $\begingroup$ What have you tried? What research have you done? I expect you to do a significant amount of research before asking, and to show us what you've tried and what you know in the question. Are you familiar with continued fractions? (This might affect the level of answer.) Also, what's the context in which you ran across this question? $\endgroup$ – D.W.♦ Aug 27 '14 at 16:16
  • $\begingroup$ I'm familiar with continued fractions and have tried a similar (but less efficient) approach comparable to Pseudonym's approach below. My research on this question didn't take me a long way - I couldn't even find out whether there always is an optimal answer. (I.e. I didn't find out whether there are $m<n\in \mathbb{N}$ such that for all $u,v\in U$ there are $u',v'\in U$ such that $|\frac{m}{n} - (u'+v')| < |\frac{m}{n} - (u'+v')|$.) There seems to be little research on approximations by sums of positive or negative unit fractions. $\endgroup$ – Dominic van der Zypen Aug 28 '14 at 6:42
1
$\begingroup$

Here's a method that gets close. Do a continued fraction expansion of $\frac{m}{n}$:

$$\frac{m}{n} = \frac{1}{a + \frac{1}{b + \epsilon}} \approx \frac{1}{a + \frac{1}{b}} = \frac{1}{a} - \frac{1}{a(1 + ba)}$$

If $\epsilon$ is small, then this is probably very close to optimal if not optimal in most cases.

The method fails when the truncated continued fraction approximation isn't very good. Take $\frac{15403}{26685}$ (a rational approximation to the Euler-Mascheroni constant) as an example. The continued fraction approximation is:

$$\frac{15403}{26685} = \frac{1}{1 + \frac{1}{1 + \epsilon}}$$

Which suggests:

$$\frac{15403}{26685} \approx \frac{1}{1} - \frac{1}{2}$$

But clearly $\frac{1}{2} + \frac{1}{14}$ is closer.

I would wager that the worst case for any method is the conjugate golden ratio $\phi' = \frac{\sqrt{5} - 1}{2}$. This isn't rational (in fact it's the "most" irrational number in a technical sense; find its continued fraction expansion if you're curious), but you can get arbitrarily close by choosing $m$ and $n$ to be consecutive Fibonacci numbers, e.g. $\frac{4181}{6765}$. The best approximation I could find is $\frac{1}{2} + \frac{1}{9}$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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