egyptian fractions...
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 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: http://scienceblogs.com/goodmath/2006/11/egyptian_fractions.php http://groups.google.com/group/mathfuture/browse_thread/thread/97511940cccd5... """ 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
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:
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
On Wed, Jun 1, 2011 at 17:52, Gregor Lingl <gregor.lingl@aon.at> 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.
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 Edu-sig@python.org 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
On Wed, Jun 1, 2011 at 2:59 PM, Edward Cherlin <echerlin@gmail.com> 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
On Wed, Jun 1, 2011 at 18:56, Kirby Urner <kurner@oreillyschool.com> wrote:
On Wed, Jun 1, 2011 at 2:59 PM, Edward Cherlin <echerlin@gmail.com> 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
On Wed, Jun 1, 2011 at 2:52 PM, Gregor Lingl <gregor.lingl@aon.at> 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
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
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
participants (5)
-
Edward Cherlin -
Gregor Lingl -
kirby urner -
Kirby Urner -
Litvin