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.

  • 0
    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?2012-09-19
  • 2
    **Exact** will be very tough. For example, it is not known whether every $\dfrac{4}{n}$ can be done with three or fewer.2012-09-19
  • 0
    @gt6989b I guess the most interesting would be an algorithm to find the $\{n_i\}$ given a specific $m$ and $n$.2012-09-19

2 Answers 2

1

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.

1

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

  • 1
    Egyptian fractions have the added constraint that all the denominators must be different, so it's not quite what I was looking for.2012-09-19
  • 0
    @Arthur: Still, many of the same basic ideas apply, such as the greedy algorithm.2012-09-19