2
$\begingroup$

Given a fraction $0 < \frac{m}{n} < 1$, what is the lowest $k$ so that you can write $$ \frac{m}{n} = \sum_{i=1}^k \frac{1}{n_i} $$ with the $n_i$ not neccessarily distinct? Obviously, $m$ is an upper bound. To see that you can do better than $m$ in some cases, $\frac{5}{6} = \frac{1}{2} + \frac{1}{3}$. That's where I'm stuck at the moment.

$\endgroup$
  • $\begingroup$ Sometimes you cannot do better -- the upper bound of $m$ is sharp, e.g. $\frac{2}{3}$. So what are you asking for -- an algorithm of how to come up with the optimal number? $\endgroup$ – gt6989b Sep 19 '12 at 18:48
  • 2
    $\begingroup$ Exact will be very tough. For example, it is not known whether every $\dfrac{4}{n}$ can be done with three or fewer. $\endgroup$ – André Nicolas Sep 19 '12 at 18:56
  • $\begingroup$ @gt6989b I guess the most interesting would be an algorithm to find the $\{n_i\}$ given a specific $m$ and $n$. $\endgroup$ – Arthur Sep 19 '12 at 19:03
1
$\begingroup$

Let $F(m/n)$ be the least $k$ for $m/n$ (assumed to be a fraction in lowest terms). Since we know $F(m/n) \le m$, at least one of the summands $1/n_i$ in an optimal expression will have $1/n_i \ge 1/n $ and thus $n_i \le n$. So $F(1/n) = 1$ and otherwise $F(m/n) = \min \{ 1 + F(m/n - 1/j): j=1 \ldots n\}$. This should lead to a dynamic programming algorithm. Not very efficient, though.

$\endgroup$
1
$\begingroup$

These are called Egyptian fractions and there is a large literature on them.

$\endgroup$
  • 1
    $\begingroup$ Egyptian fractions have the added constraint that all the denominators must be different, so it's not quite what I was looking for. $\endgroup$ – Arthur Sep 19 '12 at 19:05
  • $\begingroup$ @Arthur: Still, many of the same basic ideas apply, such as the greedy algorithm. $\endgroup$ – André Nicolas Sep 19 '12 at 19:13

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.