<html>
<body>
At 04:52 PM 6/1/2011, kirby urner wrote:<br>
<blockquote type=cite class=cite cite="">What I've been up to lately,
besides teaching Python 24/7,<br>
is debating with the Egyptologists whether computer science<br>
really has an algorithm for "Egyptian Fractions". Milo is
<br>
arguing it doesn't and the consensus seems to be with <br>
him for now. Fibonacci published what's today often called<br>
"the greedy algorithm" (though that's more the genre than<br>
the specimen) and I'm including that in Python below.</blockquote><br>
Hi, Kirby.<br><br>
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.<br><br>
Given p/q, where q is a prime, first find n such that<br>
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<tt>//</tt>q and P<tt>%</tt>q.<br><br>
For example p/q = 5/11 ==> n = 3 ==> Q = 11*(2^3) =
88 ==><br>
P = 5*(2^3) = 40 = 3 * 11 + 7 = (1 + 2) * 11 + 1 + 2 + 4
==><br>
5/11 = 40/88 = 1/8 + 1/4 + 1/88 + 1/44 + 1/22.<br><br>
The number of fractions in this method does not exceed the number of
proper divisors of Q, which is 2n+1<br>
which is less than 2 * log[base 2](q) + 1 -- not too bad. The
denominators of the fractions are below q^2.<br><br>
Gary Litvin<br>
<a href="http://www.skylit.com/" eudora="autourl">www.skylit.com<br>
</a></body>
</html>