Count Like an Egyptian (Part II)

In a previous entry, we discussed egyptian fractions and, in particular, a greedy algorithm to convert them. We noticed that, once in a while, the greedy algorithm generates a really large denominator, despite harmless-looking fractions:

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

So, I had an idea to, maybe, minimize the size of the maximum denominator.

The idea I had was to remove a unit fraction that leaves an “easy” remainder, so that the remainder would need fewer unit fractions to be expressed. I started with the decomposition

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

where k is the smallest integer such that b divides ka-1. For example, with \frac{4}{5}, we find k=5, and we have

\displaystyle \frac{4}{5}=\frac{3}{4}+\frac{1}{20}

Now, does it work? Does it generates fewer terms? Are the denominator smaller?

* *

Well, let us plot the number of fractions for the greedy algorithm vs the proposed decomposition:


We see that the proposed decomposition generates, very often, an absurdly high number of terms compared to the greedy algorithm. That’s not entirely surprising since the k decomposition produces relatively small fractions. OK, what about we get the canonical factorization of the denominator and use the smallest prime raised to its maximum power? This one works seems to work better:


…except when the denominator is a prime number. It simply doesn’t work, because, for example, \frac{3}{19} is expressed as \frac{1}{19}+\frac{1}{19}+\frac{1}{19}, which is not a cromulent solution.

* *

So what’s the conclusion? The conclusion is that heuristics do not always work. The greedy algorithm sometimes yield surprisingly large denominator, my first proposed solution using an integer k to split a ratio \frac{a}{b} sometimes generates a very large number of fractions while also generating absurdly large denominators (albeit somewhat more rarely than the greedy algorithm), and the factorization-based heuristics fails when the denominator is a prime number…

To be continued…

One Response to Count Like an Egyptian (Part II)

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

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: