The ancient egyptian
notation for fraction
s. All fractions were expressed as a sum
s. For instance, 2/3 = 1/2+1/6
, and 7/13=1/2 + 1/26 = 1/3 + 1/5 + 1/195
. It is interesting
that there is always such a representation for a fraction. In fact, always taking the largest reciprocal still smaller than the remainder is guaranteed to terminate
! (This is the greedy algorithm
for the problem)
This naive algorithm is, however, very awkward in practice, as it requires huge denominators. For instance, it gives 47/60 = 1/2 + 1/4 + 1/30, whereas 47/60 = 1/3 + 1/4 + 1/5 would be much better.
There are many hard problems related to this representation. For instance, if we restrict ourselves to using reciprocals of odd numbers, we'll always get a fraction with an odd denominator. But is it true that any fraction with odd denominator can be expressed as an egyptian fraction using only odd numbers? It turns out that this is true (a previous version of the writeup claimed this is an unsolved problem, but it isn't one).