any rational number is a sum of unit fractions
Representation
Any rational number between 0 and 1 can be represented as a sum of different unit fractions. This result was known to the Egyptians, whose way for representing rational numbers was as a sum of different unit fractions.
The following greedy algorithm can represent any as such a sum:
- 1.
-
2.
Output as the next term of the sum.
-
3.
Continue from step 1, setting
Proof of correctness
Proof.
The algorithm can never output the same unit fraction twice. Indeed, any selected in step 1 is at least 2, so – so the same cannot be selected twice by the algorithm, as then could have been selected instead of .
It remains to prove that the algorithm terminates. We do this by induction on .
- For :
-
The algorithm terminates immediately.
- For :
-
The selected in step 1 satisfies
So
and – by the induction hypothesis, the algorithm terminates for .
∎
Problems
-
1.
The greedy algorithm always works, but it tends to produce unnecessarily large denominators. For instance,
but the greedy algorithm selects , leading to the representation
-
2.
The representation is never unique. For instance, for any we have the representations
So given any one representation of as a sum of different unit fractions we can take the largest denominator appearing 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 |
---|---|
Canonical name | AnyRationalNumberIsASumOfUnitFractions |
Date of creation | 2013-03-22 12:48:31 |
Last modified on | 2013-03-22 12:48:31 |
Owner | Mathprof (13753) |
Last modified by | Mathprof (13753) |
Numerical id | 7 |
Author | Mathprof (13753) |
Entry type | Derivation |
Classification | msc 11A67 |
Synonym | Egyptian algorithm |