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.
Optimal decomposition of $\frac{m}{n}$
2
$\begingroup$
fractions
-
0Sometimes 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
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.
-
1Egyptian 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