## 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

$\alpha\leftarrow\alpha-\beta$,

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”, […]