The
ancient egyptian notation for
fractions. All fractions were expressed as a
sum of
reciprocals. 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).