Reverse Greed for Unit Fractions

Here's an interesting algorithm for expanding any fraction into a sum of unit fractions. The method seems to give quite nice expansions that look rather "Egyptian". In fact, it reproduces many of the expansions listed in the Rhind Papyrus, etc. But, in addition, it easily generates a nice four-term expansion of 31/311 and in general seems to work well even on "difficult" fractions. Still, it's so simple that it could have been known to the ancient Egyptians.

The method may seem counter-intuitive, because we tend to think in "greedy" ways, i.e., when trying to split up a fraction 7/13 our first instinct is to subtract 1/2 and then try to squeeze smaller unit fractions into the remainder. Maybe this is a "modern" thought pattern. It actually makes more sense to choose the smallest parts first, and work toward the larger parts. The method, which might be called the Reverse Greedy algorithm, is just this:

Let N/QR be a fraction in lowest terms with Q > 1 and (Q,R) = 1, and let x,y be the smallest positive solution of Nx − Qy = R. Then 1/Qx is a term in the expansion, with remainder y/Rx. Expand this remainder and iterate until reaching a unit fraction remainder.

This is actually even simpler than it sounds. Take for example the "difficult" fraction 31/311. Here we have N = 31, Q = 311, R = 1. (Notice that the denominator QR = 311, and we require Q > 1 and also that Q,R must have no common factor. Therefore, we set Q = 311 and R = 1.) So for this first round we need the smallest integer solution of 31x − 311y = 1. It's easy to see (either by trial and error, or by the Euclidean algorithm) that the smallest solution is x = 301, y = 30. Therefore, the first term in our expansion is 1/Qx = 1/[(311)(301)] = 1/93611, with the remainder y/Rx = 30/[(1)(301)]. In other words, we've shown that

Now we apply the same procedure to 30/301, which gives

Then we apply the procedure to 11/112 to find

and we're done.  We have found

Notice that we found these terms in reverse order, beginning with 1/93611. Admittedly this denominator is larger than 8708 (see below), but it is the smallest possible if we allow only one of the denominators to be a multiple of 311. Also, the 2nd and 3rd terms are smaller than in the 8708 solution.

Interestingly, this method gives 2/91 = 1/70 + 1/130 and many others from the Rhind 2/n table. For another example, consider the fraction 163/431, which seems like it might be difficult. The algorithm quite simply gives the expansion

Comparing this method to the 10 methods that David Eppstein describes on his web page, we notice that in one special circumstance it gives the same results as the continued fraction method. The special circumstance is if all the values of R in the process equal 1. This rarely happens, because it implies none of the denominators in the sequence can be factored into non-trivial coprime factors. It just so happens that one of David's examples, 18/23, is such a case, so both methods give

However, for 7/15 the basic Continued Fraction Method gives

whereas the Reverse Greedy Algorithm gives

which seems much closer to the Egyptian style. (This is even better than what David calls the Grouped Continued Fraction Method, which is a quite complicated algorithm, and gives 7/15 = 1/3 + 1/9 + 1/45.) All in all, this new method seems to consistently produce representations that are very close to the spirit of the historical Egyptian unit fractions.

One interesting aspect of the algorithm described above is that, in order to yield unique results, we must include a rule for factoring the denominators. Interestingly, with Q = 1 it's equivalent to the Greedy Method, whereas with R = 1 it's equivalent to the Continued Fraction Method. Thus it appears that a wide variety of methods can be expressed in terms of the above algorithm together with some fixed rule for factoring the denominators.

We can classify these as "local" algorithms, i.e., methods that proceed in a step-wise manner by optimizing some function of the immediate remainder. This is in contrast to "global" algorithms, which optimize some function of the entire completed expansion. I suspect that any sort of general global optimization is NP-complete, and that no local algorithm can guarantee a globally optimum result in every case.

The stipulation that (Q,R) = 1 was included as sort of an example of one way we could restrict the choices (not meant to imply that this condition is required for Nx – Qy = R to be solvable), but of course it doesn't completely specify the decomposition of denominators that are divisible by more than two distinct primes. My first implementation of this method set Q equal to the highest power of the largest prime dividing the denominator, the idea being to completely eliminate the largest prime from the denominator of the remainder. (By the way, to answer one of David Eppstein's questions, this explains why the method gave R = 1 at each step of the expansion of 18/23, because the denominators were all prime powers.)

Of course, we're free to base the algorithm on any fixed factoring rule we choose. David Eppstein has experimented with a couple of different rules. I've tried dropping the (Q,R) = 1 requirement and just choosing the factors with Q > R such that Q−R is minimized. This rule gives an algorithm that is closely related to the "Fibonacci" methods.

Overall, the basic algorithm can be regarded as a means of unifying and classifying all the various "local" methods, each corresponding to a particular rule of factorization. Given a set of expansions from some historical document, we can check to see if some fixed factorization rule generates all those expansions.

From a historical standpoint, it seems (from what little I know of the surviving documentary evidence) that the ancient Egyptians didn't use any single rule for generating their unit fraction expansions. As a result, the small quantity of material must be sub-divided into even smaller sets of examples of any particular method, which makes it almost impossible to build conclusive arguments about the thought processes they may have used. If the 2/n table in the Rhind Papyrus had gone up to 2/1001 instead of just 2/101 we would be in a much better position to "reverse engineer" their methods.

Recall that we found a unit fraction expansion of 31/311 with largest denominator equal to 93611. Although several local methods yield this four-term expansion, I've not found one that gives the expansion with smallest max denominator. However, we can expand our analysis in a global direction by expanding into two unit fractions at once.

Given a fraction N/D in lowest terms, we begin with some factorization of the denominator D = QR and then deduct two unit fractions from N/D, both of which have denominators divisible by Q. (Historically this comes from the fact that many of the Egyptian expansions seem to have the final two or even three denominators divisible by a large prime factor of D.) So we have

which can be written in the form

We want to eliminate Q from the denominator of n/d, so we have the condition

which has the smallest solution x = 9, y = 28, leaving the remainder 25/252. We can then check by the usual method to see if 25/252 has a two-term expansion, which it does, 1/14 + 1/36, so we have the result

So this algorithm consists of first checking for simple 2-term expansions, then (assuming none exist) expanding the first two high-order terms, and iterating on the remainder. (Obviously we still need to specify a fixed factorization rule to split QR at each stage.)

I don't imagine the ancient Egyptians practiced anything like this. It's more likely that their expansions tended to have pairs (or triples) of denominators with common factors because they produced them by multiplying binomials (or trinomials) of smaller expansions.

One more interesting fact about the ratio 31/311 is that, although it has no three-term expansion, the nearest three-term expansion differs from the true value by a unit fraction, i.e.,

where the final (negative) denominator is just the least common multiple of all the other denominators.

Return to MathPages Main Menu