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

  • 0
    @Arthur: Still, ma$n$y of the same basic i$d$eas apply, such as the gree$d$y algorithm.2012-09-19