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