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.
I'm trying to figure out of that's what's going on in Eppstein's code, which includes some from me:
Milo reminds us on mathfuture that these weren't academic pursuits for the Egyptians so much as a way of divvying up grain, other dry and liquid goods, in containers of known trusted quantities, and these tended to come in 1/something, i.e. as unit fractions.
You could pour multiple scoops of 1/88 of course, but when it comes to storage, each capsule of wheet and/or pepper needs to have a unit fraction clearly marked.
These could then be aggregated and swapped in ways that made sense the The Temple (an abstraction, used for bookkeeping purposes, similar to The House in Casino Math).
His case that the solutions weren't algorithmic is really just that they weren't exclusively algorithmic, and that where many recipes yield possible results, it's up to the "chef" to decide what's savory.
That's not a job best left to mere computers, even of the human variety.
Gotta have a nose, like chief taster for Jack Daniels (a chiefdom in some ways -- took the tour in Lynchburg that time, a side trip of the main road from Chatanooga to Nashville).
Good hearing from ya.
Ed, if you're listening, I made more waves around baseball stats as the core database for our SQL teaching courses (includes languages using DBAPI), might be on the agenda next staff meeting.
People get mixed messages about SQL: that it was designed for end users (ala MS Access), or that it's for highly skilled DBAs only, with all kinds of certification?
Schooling is about reducing the intimidation factor.
Kirby
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