At 04:52 PM 6/1/2011, kirby urner wrote:
>What I've been up to lately, besides teaching Python 24/7,
>is debating with the Egyptologists whether computer science
>really has an algorithm for "Egyptian Fractions".  Milo is
>arguing it doesn't and the consensus seems to be with
>him for now.  Fibonacci published what's today often called
>"the greedy algorithm" (though that's more the genre than
>the specimen) and I'm including that in Python below.

Hi, Kirby.

Thanks for mentioning Egyptian fractions.  I think one of the
algorithms for finding them leads to a neat programming exercise on
representing numbers in binary.

Given p/q, where q is a prime, first find n such that
2^n < q < 2^(n+1).  Then consider Q = q*(2^n).  Q has a property that
any positive integer below Q can be represented as a sum of different
proper divisors of Q.  In particular, P = p*(2^n) can be represented
that way.  This leads to a representation of p/q = P/Q as a sum of
Egyptian fractions (not necessarily the "best").  To find which
divisors of Q add up to P use binary representations of P//q and P%q.

For example p/q = 5/11  ==>  n = 3 ==> Q = 11*(2^3) = 88  ==>
P = 5*(2^3) = 40 = 3 * 11 + 7 = (1 + 2) * 11 + 1 + 2 + 4  ==>
5/11 = 40/88 = 1/8 + 1/4 + 1/88 + 1/44 + 1/22.

The number of fractions in this method does not exceed the number of
proper divisors of Q, which is 2n+1
which is less than 2 * log[base 2](q) + 1 -- not too bad.  The
denominators of the fractions are below q^2.

Gary Litvin
www.skylit.com