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

Question

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.

Answer 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.

Answer 2

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