Walk Count like an Egyptian (Part I)

The strangest aspect of the Ancient Egyptian’s limited mathematics is how they wrote fractions. For example, they could not write \frac{5}{7} outright, they wrote

\displaystyle \frac{5}{7}=\frac{1}{2}+\frac{1}{5}+\frac{1}{70},

and this method of writing fractions lead to absurdly complicated solutions to trivial problems—at least, trivial when you can write a vulgar fraction such as \frac{3}{5}. But how much more complicated is it to write \frac{1}{2}+\frac{1}{5}+\frac{1}{70} rather than \frac{5}{7}?

Let’s have a look at how to write egyptian fractions from “normal” fractions

One possible algorithm to transform a normal fraction to an egyptian fraction is a greedy algorithm. Let \alpha be the (remainder of the) fraction 0<\alpha<1 we're transforming. At each step, we find \beta=\frac{1}{k}, the largest fraction not exceeding \alpha. We write \beta as part of the solution, and set \alpha'=\alpha-\beta, and, if \alpha' is not zero, we start over again, finding the largest unit fractions that does not exceeed \alpha'.

The “hard” part is to find this largest fraction, but it turns out that

\displaystyle \beta=\frac{1}{\left\lceil \frac{1}{\alpha} \right\rceil}

gives the wanted answer. We then subtract \beta from $\alpha$, that is


and we iterate until \alpha is zero.

With this algorithm, we find, for example,

\displaystyle \frac{4}{5}=\frac{1}{2}+\frac{1}{4}+\frac{1}{20},

\displaystyle \frac{19}{20}=\frac{1}{3}+\frac{1}{9}+\frac{1}{180},

\displaystyle \frac{19}{21}=\frac{1}{2}+\frac{1}{3}+\frac{1}{14},

\displaystyle \frac{17}{29}=\frac{1}{2}+\frac{1}{12}+\frac{1}{348}.

But sometimes, trivial-looking fractions yield a surprising representation:

\displaystyle \frac{412}{1000}=\frac{1}{3}+\frac{1}{13}+\frac{1}{574}+\frac{1}{699563}!

* *

The greedy algorithm is implemented in just a few lines of Mathematica code:

Binary[x_] := 2^Floor[-Log[2, x] + 1]

Greedy[x_] := Ceiling[1/x]

Egypt[x_, F_] := If[Chop[N[x]] > 0,
  Module[{a = 1/F[x]},
   Return [Flatten[Append[{a}, Egypt[x - a, F]]]]],

Note that there are two helper functions: Greedy, that returns the largest unit fraction not exceeding the remainder, and where the denominator is just any integer, and Binary, that returns the largest unit fraction not exceeding the remainder, but where the denominator is a power of two.

* *

Decomposing fractions as the Egyptian did is cumbersome. Rudman [1] offers an explanation that is based on variations of the greedy algorithm, maybe a leftover artifact of pebble-and-stone counting. Nevertheless, adapting this algorithm to powers-of-two fractions is most trivial. In fact, just writing down the fraction in base 2 yields the desired decomposition! For example,

\displaystyle \frac{4}{5}=0.1100110011\ldots=\frac{1}{2}+\frac{1}{4}+\frac{1}{32}+\frac{1}{64}+\cdots,

as would yield a call to Egypt[4/5,Binary].

Decomposing fraction in binary does make sense from a computation point of view as long as one has a binary computer. Adding such binary fractions is easy, since all complicated denominator arithmetic is replaced by a simple bit shift—a lot easier than adding two egyptian fractions. Think: you would have to add one unit fraction of one complete fraction to a unit fraction of the other, then decompose the result as a sum of unit fractions… argh! But egyptian fractions made sense (to the Egyptians) because of their (supposed) means of computation. Today, of course, egyptian fractions are tedious since we can write directly any ratio using our ordinary fractions. They are now a mere curiosity that offers opportunities for new algorithms.

To be continued…

[1] Peter Strom Rudman — How Mathematics Happened: The First 50,000 Years — Prometheus Books, 2006.

2 Responses to Walk Count like an Egyptian (Part I)

  1. […] a previous entry, we discussed egyptian fractions and, in particular, a greedy algorithm to convert them. We noticed […]

  2. […] previous posts, I’ve looked into unit fractions, also known as “Egyptian fractions”, […]

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: