[Edu-sig] egyptian fractions...
litvin at skylit.com
Thu Jun 2 22:27:54 CEST 2011
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.
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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Edu-sig