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.

fract-length

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.

fract-denum

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}.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: