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
_______________________________________________
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig
