[Edu-sig] egyptian fractions...

[Kirby Urner]

>
>
> 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:

http://www.ics.uci.edu/~eppstein/numth/egypt/egypt.py

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/edu-sig/attachments/20110602/8f7c5ef8/attachment.html>