# Optimal decomposition of $\frac{m}{n}$

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.

• 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? – gt6989b Sep 19 '12 at 18:48
• Exact will be very tough. For example, it is not known whether every $\dfrac{4}{n}$ can be done with three or fewer. – André Nicolas Sep 19 '12 at 18:56
• @gt6989b I guess the most interesting would be an algorithm to find the $\{n_i\}$ given a specific $m$ and $n$. – Arthur Sep 19 '12 at 19:03

## 2 Answers

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.

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

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