Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
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 2

up vote 1 down vote accepted

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.

share|improve this answer

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

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.