any rational number is a sum of unit fractions
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:
be the smallest natural number for which . If , terminate.
Output as the next term of the sum.
Continue from step 1, setting
Proof of correctness
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 .
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|
|Date of creation||2013-03-22 12:48:31|
|Last modified on||2013-03-22 12:48:31|
|Last modified by||Mathprof (13753)|