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