If x is a positive rational, show that we can find distinct positive integers a_{1}, a_{2}, ... , a_{n} such that x = ∑ 1/a_{i}.

**Solution**

*Hard.*

Rather surprisingly, the simplest possible algorithm - the greedy algorithm - works: take a_{n} to be the smallest integer not already chosen so that the sum does not exceed x. This terminates after a finite number of steps.

Note that the numbers involved can be quite large even in simple cases. For example: 4 = 1/1 + 1/2 + 1/3 + ... + 1/30 + 1/200 + 1/77706 + 1/16532869712 + 1/3230579689970657935732 + 1/36802906522516375115639735990520502954652700

The key idea is that the numerator of the difference gets smaller each time and hence the process must terminate.

First, we have to get the difference under 1. So take m such that 1 + 1/2 + ... + 1/m ≤ x < 1 + 1/2 + ... + 1/(m+1). This is possible since the harmonic series diverges. If we have equality, then we are home. If not then the difference x - (1 + 1/2 + ... + 1/m) < 1/(m+1).

Let the difference x - (1/a_{1} + 1/a_{2} + ... + 1/a_{n}) be d_{n} = r_{n}/s_{n} (where r_{n} and s_{n} are integers).

So we may assume that we have picked a_{1}, ... , a_{n} and that d_{n} < 1/(a_{n} + 1). We now take a_{n+1} so that 1/a_{n+1} ≤ d_{n} < 1/(a_{n+1} - 1). Now d_{n+1} = d_{n} - 1/a_{n+1} = (r_{n}a_{n+1} - s_{n})/(s_{n}a_{n+1}). This expression may not be in lowest terms, but it is certainly *sufficient* to show that (r_{n}a_{n+1} - s_{n}) < r_{n} or d_{n}a_{n+1} - 1 < d_{n}. But that is true since d_{n}(a_{n+1} - 1) < 1. Finally, we notice that d_{n+1} < 1/(a_{n+1} + 1) is equivalent to d_{n} - 1/a_{n+1} < 1/(a_{n+1} + 1), which is true since 1/(a_{n+1} - 1) - 1/a_{n+1} < 1/(a_{n+1} + 1), since a_{n+1} > 1.

© John Scholes

jscholes@kalva.demon.co.uk

26 Nov 1999