# any rational number is a sum of unit fractions

## Representation

The following greedy algorithm can represent any $0\leq\frac{a}{b}<1$ as such a sum:

1. 1.

Let

 $n=\left\lceil\frac{b}{a}\right\rceil$

be the smallest natural number  for which $\frac{1}{n}\leq\frac{a}{b}$. If $a=0$, terminate.

2. 2.

Output $\frac{1}{n}$ as the next term of the sum.

3. 3.

Continue from step 1, setting

 $\frac{a^{\prime}}{b^{\prime}}=\frac{a}{b}-\frac{1}{n}.$

## Proof of correctness

###### Proof.

The algorithm can never output the same unit fraction twice. Indeed, any $n$ selected in step 1 is at least 2, so $\frac{1}{n-1}<\frac{2}{n}$ – so the same $n$ cannot be selected twice by the algorithm, as then $n-1$ could have been selected instead of $n$.

It remains to prove that the algorithm terminates. We do this by induction  on $a$.

For $a=0$:

The algorithm terminates immediately.

For $a>0$:

The $n$ selected in step 1 satisfies

 $b\leq an

So

 $\frac{a}{b}-\frac{1}{n}=\frac{an-b}{bn},$

and $0\leq an-b – by the induction hypothesis, the algorithm terminates for $\frac{a}{b}-\frac{1}{n}$.

## Problems

1. 1.

The greedy algorithm always works, but it tends to produce unnecessarily large denominators. For instance,

 $\frac{47}{60}=\frac{1}{3}+\frac{1}{4}+\frac{1}{5},$

but the greedy algorithm selects $\frac{1}{2}$, leading to the representation

 $\frac{47}{60}=\frac{1}{2}+\frac{1}{4}+\frac{1}{30}.$
2. 2.

The representation is never unique. For instance, for any $n$ we have the representations

 $\frac{1}{n}=\frac{1}{n+1}+\frac{1}{n\cdot(n+1)}$

So given any one representation of $\frac{a}{b}$ as a sum of different unit fractions we can take the largest denominator appearing $n$ and replace it with two (larger) denominators. Continuing the process indefinitely, we see infinitely many such representations, always.

Title any rational number is a sum of unit fractions AnyRationalNumberIsASumOfUnitFractions 2013-03-22 12:48:31 2013-03-22 12:48:31 Mathprof (13753) Mathprof (13753) 7 Mathprof (13753) Derivation msc 11A67 Egyptian algorithm