## Count like an Egyptian (Part III)

In previous posts, I’ve looked into unit fractions, also known as “Egyptian fractions”, fractions where the numerator is $1$ and the denominator $n$, some integer. We have noticed that finding good representation for a fraction $a/b$ as a sum of unit fraction is not as trivial as it may first seem. Indeed, we noticed that the greedy algorithm, the one that always pick the largest unitary fraction that does not exceed the rest as the next term, may lead to long series of unit fractions, sometimes with large denominators, even for simple fraction. For example,

$\displaystyle \frac{412}{1000}=\frac{103}{250}=\frac{1}{3}+\frac{1}{13}+\frac{1}{574}+\frac{1}{699563}$.

In a previous post, I suggested decomposing $a/b$ in an “easy way”, which was often better than the greedy algorithm. Surely, we can do better, but how?

What about depth- or breath-first exhaustive search? Will that do much better? And what should we measure exactly? Lengths of the decompositions? Largest denominators? Sure, both!

*
* *

So let’s recapitulate the three methods:

• Greedy. At each iteration, we pick the largest unit fraction that doesn’t exceed the remainder. For example,

$\displaystyle \frac{2}{3}=\frac{1}{2}+\frac{1}{6}$.

• Decomposition. We want to express fractions as

$\displaystyle \frac{a}{b}=\frac{ka}{kb}=\frac{ka-1}{kb}+\frac{1}{kb}$.

Here, $k$ is chosen such that $b$ divides $ka-1$. This requires solving a congruence equation, which leaves us with candidates $1$ to $b-1$ for $k$. Not sure how to solve this very efficiently.

• Exhaustive search. By a method of your choice (depth- or breadth-first search) explore all valid combinations of fractions to find one that has all positive terms, whose sum does not exceed the fraction to express. This doesn’t mean the solution is different than the greedy method, but it may be. For example, with the greedy heuristic, we find that

$\displaystyle\frac{5}{121}\approx\frac{1}{25}+\frac{1}{757}+\frac{1}{763309}$,

up to machine precision, while exhaustive search yields

$\displaystyle\frac{5}{121}=\frac{1}{33}+\frac{1}{99}+\frac{1}{1089}$,

exactly.

*
* *

So now let’s compare the results of the different decompositions against two criteria: the largest denominator found, and the length of the decomposition. If you have simultaneously small largest denominators and short decompositions, the method yields better results.

Note that here, the greedy method is limited to machine precision, or basically one part by billion. If the fraction is “close enough”, the greedy method stops and gives a good approximation. The error for $\latex 5/121$, the example give above, is $2/1747920361825$. That’s “close enough”. The two other methods go on until they reach a remainder of zero.

The first plot shows the length of the decomposition, in the numbers of terms. The “decomposition” method may yield an inordinate amount of terms. While the greedy method yields more terms than the exhaustive searches (either by shortest decomposition or by smallest largest denominator), it fares much better than the “decomposition”. Unsurprisingly, exhaustive search for shortest decomposition always finds the shortest decomposition; sometimes the search for smallest largest denominator coincides with it.

The second criterion is maybe more interesting: the smallest largest denominator in the decomposition. Certainly for pen-and-paper calculations, the smaller are the numbers involved, the better.

Pay attention to this detail: it’s a log-plot. The greedy and the decomposition methods both yield very large largest denominators. The two exhaustive searches coincide often on the decomposition with the smallest largest denominator and the shortest decomposition. That’s probably the one that the most useful.

*
* *

So, in addition of the fun of exploring “Egyptian” fractions, are they of any use?

If you take a “modernist” approach, approximating, or expressing exactly, an arbitrary fraction by a sum of unit fractions is pretty pointless. Indeed, it doesn’t make much of a difference for the CPU to compute $\frac{a}{b}x$. Unless, of course, the CPU is really under-powered, it may be better to just divide by small denominators and compute the sum. I think it’s unlikely, however.

The use I can see, is when you’re trying to figure out the asymptotic behavior of some function. It may be more interesting to work with

$\displaystyle \frac{1}{2}+\frac{1}{4}+\frac{1}{68}$

and discard the $\frac{1}{68}$ than to work with $\frac{13}{17}$.