egyptian fractions...

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

egyptian fractions...

kirby urner-4

Hey Jeff, your question about controlling the turtle's screen 
might have been just the ticket in my attempts to control
chaos, namely G. Lingl's chaos.py, which demonstrates 
sensitivity to initial conditions is a plus if you want your 
algebra to stay on the same page as itself, per equalities
that won't be equal in the real world.  I'm hoping to throw 
that into site-packages on the back end at OST, along with
all those baseball stats in SQL.  It's all done with turtles
(Gregor's thing) and is brilliant, here's a link:


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.

At first I though my job would be to subclass the Fraction
class in fractions, delegating the nuts and bolts to an 
internal Fraction but adding this .egyptian( ) method
(really pseudo).  With that in mind, I storyboarded this
science fiction session (not yet real) which is another 
way of saying I applied the "agile" principle of "test 
driven development":

>>> from unitfractions import Fraction
>>> p = Fraction(5,121)
>>> type(p)
<class 'unitfractions.Fraction'>
>>> p
Fraction(5, 121)
>>> r = p.egyptian( )  # pseudo-egyptian results of Fibonacci-published algorithm
>>> r 
(Fraction(1,25), Fraction(1,757), Fraction(1,763309), Fraction(1,873960180913), Fraction(1,1527612795642093418846225))
>>> sum(r)
Fraction(5, 121)

I later decided there was no point trying to maintain the
appearance of a whole new class, and that existing
Fraction objects should just be fed to this greedy algorithm 
directly, giving a tuple of Fraction outputs. 

Not much code involved.  Keep it Simple (another 
"agile" precept).

From the original thread:

"""
On second thought, I think subclassing a fractions.Fraction is overkill.  As soon
as said subclass participates in numeric relations with its fellow Fractions
(of the ordinary kind), it's going to spawn ordinary Fractions (ancestor class).  

Maintaining an entirely new type just for this one feature is not worth the effort, 
given likely arithmetic relations with peers.

Also, I'm not a huge fan of recursion where iteration is just as straightforward.
In the case of Fibonacci's greedy algorithm, there's like nothing to it:

"""
OST Skunkworks:
Pseudo-Egyptian Fractions
See:
"""

from fractions import Fraction
from math import ceil

def greedy(q):
    """return unit fraction expansion of fractions.Fraction q,
    using Fibonacci's 'greedy algorithm' -- non-recursive"""

    results = []    

    while q > 0:
        if q.numerator == 1:
            results.append(q)
            break
        x = Fraction(1,ceil(q.denominator / q.numerator))
        q = q - x
        results.append(x)                
    return tuple(results)

def _test( ):
    """
    >>> greedy(Fraction(5,121))
    (Fraction(1, 25), Fraction(1, 757), Fraction(1, 763309), Fraction(1, 873960180913), Fraction(1, 1527612795642093418846225))
    >>> greedy(Fraction(4,5))
    (Fraction(1, 2), Fraction(1, 4), Fraction(1, 20))
    >>> greedy(Fraction(9,31))
    (Fraction(1, 4), Fraction(1, 25), Fraction(1, 3100))
    >>> greedy(Fraction(21,50))
    (Fraction(1, 3), Fraction(1, 12), Fraction(1, 300))
    >>> greedy(Fraction(1023, 1024))
    (Fraction(1, 2), Fraction(1, 3), Fraction(1, 7), Fraction(1, 44), Fraction(1, 9462), Fraction(1, 373029888))
    """
    print("testing complete")

if __name__ == "__main__":
    import doctest
    doctest.testmod()    
    _test()
    
Note that I'm calling these "pseudo Egyptian" -- not claiming there's any simple
algorithmic solution that'll work best in all cases.  Computer scientists and
Milo appear to be on the same side on this one.
"""

The threads on all this may be dredged up from an obscure Google 
group named mathfuture, one of the Droujkova facilities, and as 
usual productive.

Kirby


_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: (egyptian fractions...) the turtle part: chaos.py

Gregor Lingl-2


Am 01.06.2011 22:52, schrieb kirby urner:

>
> Hey Jeff, your question about controlling the turtle's screen
> might have been just the ticket in my attempts to control
> chaos, namely G. Lingl's chaos.py, which demonstrates
> sensitivity to initial conditions is a plus if you want your
> algebra to stay on the same page as itself, per equalities
> that won't be equal in the real world.  I'm hoping to throw
> that into site-packages on the back end at OST, along with
> all those baseball stats in SQL.  It's all done with turtles
> (Gregor's thing) and is brilliant, here's a link:
>
> http://www.4dsolutions.net/ocn/python/OST/chaos.py
>
>
Hi Kirby,

it's fine that you "host" a slightly amended version of chaos.py
on your website.

The original file is part of the demo that ships with Python and
the turtledemo has been moved into  the Lib-directory of the
standard distribution.

Some of these demo-scripts suffer from (more or less minor :-) )
quirks or deficiencies and could be amended in this or that way.

I think that such amendments should go into Python 3.3. So if
you or anybody else have any ideas, complaints or - as shown here -
propositions or results, please let's discuss them, so the turtledemo
can obtain not only a demo- but also an enhaced educational value.

Best regards

Gregor


_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: (egyptian fractions...) the turtle part: chaos.py

Mokurai
On Wed, Jun 1, 2011 at 17:52, Gregor Lingl <[hidden email]> wrote:

>
>
> Am 01.06.2011 22:52, schrieb kirby urner:
>>
>> Hey Jeff, your question about controlling the turtle's screen
>> might have been just the ticket in my attempts to control
>> chaos, namely G. Lingl's chaos.py, which demonstrates
>> sensitivity to initial conditions is a plus if you want your
>> algebra to stay on the same page as itself, per equalities
>> that won't be equal in the real world.  I'm hoping to throw
>> that into site-packages on the back end at OST, along with
>> all those baseball stats in SQL.  It's all done with turtles
>> (Gregor's thing) and is brilliant, here's a link:

Baseball stats and turtles? That's something I have been wishing for.
I think that the best way to interest children in probability and
statistics is sports, including published data and the book Money
Ball. Also Nate Silver of the New York Times Five Thirty Eight blog,
one of the best analysts of political races (though not of policy),
started out in poker and sports.

I would like to see your work, and discuss with you and various other
people creating an OER with it in the Sugar Labs Replacing Textbooks
project.

>> http://www.4dsolutions.net/ocn/python/OST/chaos.py
>>
>>
> Hi Kirby,
>
> it's fine that you "host" a slightly amended version of chaos.py
> on your website.
>
> The original file is part of the demo that ships with Python and
> the turtledemo has been moved into  the Lib-directory of the
> standard distribution.
>
> Some of these demo-scripts suffer from (more or less minor :-) )
> quirks or deficiencies and could be amended in this or that way.
>
> I think that such amendments should go into Python 3.3. So if
> you or anybody else have any ideas, complaints or - as shown here -
> propositions or results, please let's discuss them, so the turtledemo
> can obtain not only a demo- but also an enhaced educational value.
>
> Best regards
>
> Gregor
>
>
> _______________________________________________
> Edu-sig mailing list
> [hidden email]
> http://mail.python.org/mailman/listinfo/edu-sig
>



--
Edward Mokurai (默雷/धर्ममेघशब्दगर्ज/دھرممیگھشبدگر ج) Cherlin
Silent Thunder is my name, and Children are my nation.
The Cosmos is my dwelling place, the Truth my destination.
http://wiki.sugarlabs.org/go/Replacing_Textbooks
_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: (egyptian fractions...) the turtle part: chaos.py

kirby urner-4
In reply to this post by Gregor Lingl-2
On Wed, Jun 1, 2011 at 2:52 PM, Gregor Lingl <[hidden email]> wrote:

Hi Kirby,

it's fine that you "host" a slightly amended version of chaos.py
on your website.


Thanks Gregor.  I've also got John Zelle's graphics.py in the docket.

Having any backend code is a somewhat new idea.  I'm trying
to keep a toe hold for Tk, as Eclipse is regarded as "heavy" and
if we didn't need widget programming, it'd probably be gone.

I think Tk widget programming is valuable exercise with many
transferable skills, for times when you're using other widget 
libraries.  Gives important insights into IDLE as well, which
for better or worse is still what many use out of the box.

We had threads here earlier about dropping IDLE from the 
standard distro and swapping in something for leading edge.  No 
candidates came forward though, vindication of Tk in a lot
of ways (as a cross-platform solution).
 
The original file is part of the demo that ships with Python and
the turtledemo has been moved into  the Lib-directory of the
standard distribution.


I've done very few experiments with turtles on the OST server.
None of the current Python track courses require it.  Tk, however,
is used.  In principle, the turtle stuff, including chaos, should run.

My problem is when I run chaos, I'm left with an open window
in the background that I can't seem to close.  This is launching
from inside Eclipse, which is usually pretty good with Tk 
applications (a major focus in the 2nd course, mixed in with
SQL).

 
Some of these demo-scripts suffer from (more or less minor :-) )
quirks or deficiencies and could be amended in this or that way.

I think that such amendments should go into Python 3.3. So if
you or anybody else have any ideas, complaints or - as shown here -
propositions or results, please let's discuss them, so the turtledemo
can obtain not only a demo- but also an enhaced educational value.


I have no complaints.  Just wanting to keep Tk on life support, as an
aspect of a curriculum I'm helping shape.

If we use graphics.py, it'll probably to do some black and orange 
brick patterns like in New Kind of Science (Wolfram).  I'm already
doing all 256 rules in "ascii art".  Quoting from a console:

import sys; print('%s %s' % (sys.executable or sys.platform, sys.version))
C:\Python\python.exe 3.1.1 (r311:74483, Aug 17 2009, 17:02:12) [MSC v.1500 32 bit (Intel)]
import ost
from ost.nks import *
Traceback (most recent call last):
  File "<console>", line 1, in <module>
  File "\\beam\software\Python4\site-packages\ost\nks.py", line 6, in <module>
    from lifegame import Sensor
ImportError: No module named lifegame
import ost.lifegame
Traceback (most recent call last):
  File "<console>", line 1, in <module>
  File "\\beam\software\Python4\site-packages\ost\lifegame.py", line 8, in <module>
    from farmworld import Farm, Tractor, wordplow
ImportError: No module named farmworld
import ost.farmworld
import ost.lifegame
Traceback (most recent call last):
  File "<console>", line 1, in <module>
  File "\\beam\software\Python4\site-packages\ost\lifegame.py", line 8, in <module>
    from farmworld import Farm, Tractor, wordplow
ImportError: No module named farmworld

Getting nowhere here.  This is a student server and may not have my latest 
commits to CVS.  Sorry...

Kirby
 
Best regards

Gregor


_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: (egyptian fractions...) the turtle part: chaos.py

Kirby Urner-6
In reply to this post by Mokurai
On Wed, Jun 1, 2011 at 2:59 PM, Edward Cherlin <[hidden email]> wrote:

Baseball stats and turtles? That's something I have been wishing for.
I think that the best way to interest children in probability and
statistics is sports, including published data and the book Money
Ball. Also Nate Silver of the New York Times Five Thirty Eight blog,
one of the best analysts of political races (though not of policy),
started out in poker and sports.

Yes, I remember your interest.

Several of our courses touch on SQL here and there, and when it comes
to having some canned, pre-existing tables on the back end, I can 
think of fewer richer data mines that the aggregating pool of 
baseball stats.  I've floated this by other staff and know I have an
ally in one of the editors.  Question is:  are baseball stats available
for MySQL in some open source format, or locked up under lock 
and key by proprietary dot com pay-per-view services?

In a Norman Rockwell future where America gives lip service to 
appreciating education, there'd be no problem freely accessing all
these numbers, copying them to the home hard drive.  Maybe 
this already exists.  I'm in the beginning stages.
 

I would like to see your work, and discuss with you and various other
people creating an OER with it in the Sugar Labs Replacing Textbooks
project.


I'm trying to condense a lot of concepts into a dense compacted
set of modules that aren't too daunting to read, and that don't hide
a lot of functionality.  The metaphor of a Turtle has been replaced
with a Tractor in a field (ascii 2d matrix / array).  This isn't about
displacing turtle graphics, it's about creating an analogy that's 
even simpler (more primitive).

Kirby


_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: (egyptian fractions...) the turtle part: chaos.py

Mokurai
On Wed, Jun 1, 2011 at 18:56, Kirby Urner <[hidden email]> wrote:

> On Wed, Jun 1, 2011 at 2:59 PM, Edward Cherlin <[hidden email]> wrote:
>>
>> Baseball stats and turtles? That's something I have been wishing for.
>> I think that the best way to interest children in probability and
>> statistics is sports, including published data and the book Money
>> Ball. Also Nate Silver of the New York Times Five Thirty Eight blog,
>> one of the best analysts of political races (though not of policy),
>> started out in poker and sports.
>
> Yes, I remember your interest.
> Several of our courses touch on SQL here and there, and when it comes
> to having some canned, pre-existing tables on the back end, I can
> think of fewer richer data mines that the aggregating pool of
> baseball stats.  I've floated this by other staff and know I have an
> ally in one of the editors.  Question is:  are baseball stats available
> for MySQL in some open source format, or locked up under lock
> and key by proprietary dot com pay-per-view services?

Major League Baseball asserts copyright ownership over everything to
do with the American and National Leagues that has not passed into the
public domain. For books that means almost anything since 1922. I have
no idea who owns rights to the Negro League data and to the data from
other countries. I don't know the rules for databases in any detail,
although I have heard of court cases declaring that facts cannot be
copyrighted, only their specific expression, and that not always. You
can buy the complete set of data for US baseball, going back about 150
years, on a CD-ROM.

http://www.allprosoftware.com/sb/

has commercial products for seven sports, at $70 or so.

We would also need soccer and cricket, at least, which this US company
does not offer, and no doubt other sports and games. The Elo
international chess rating system is a major work. It has spun off
systems for many other tournament games. I have no idea who owns what
internationally, given the vast interlocking structure of
international governing bodies, leagues, and tournaments.

> In a Norman Rockwell future where America gives lip service to
> appreciating education, there'd be no problem freely accessing all
> these numbers, copying them to the home hard drive.  Maybe
> this already exists.  I'm in the beginning stages.

Some of it is unquestionably available.

>> I would like to see your work, and discuss with you and various other
>> people creating an OER with it in the Sugar Labs Replacing Textbooks
>> project.
>>
>
> I'm trying to condense a lot of concepts into a dense compacted
> set of modules that aren't too daunting to read, and that don't hide
> a lot of functionality.  The metaphor of a Turtle has been replaced
> with a Tractor in a field (ascii 2d matrix / array).

Have you considered Unicode?

> This isn't about
> displacing turtle graphics, it's about creating an analogy that's
> even simpler (more primitive).

It should still work for teaching many CS topics.

> Kirby

Have you ever looked at Befunge, a 2D programming language with a
mobile instruction pointer and instructions for changing its
direction? It has been described as "a cross between FORTH and
Lemmings." ^_^

--
Edward Mokurai (默雷/धर्ममेघशब्दगर्ज/دھرممیگھشبدگر ج) Cherlin
Silent Thunder is my name, and Children are my nation.
The Cosmos is my dwelling place, the Truth my destination.
http://wiki.sugarlabs.org/go/Replacing_Textbooks
_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: egyptian fractions...

Litvin-2
In reply to this post by kirby urner-4
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
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: egyptian fractions...

Kirby Urner-6

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


_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig