[Edu-sig] Pythonic Math must include...
kirby urner
kirby.urner at gmail.com
Fri Jan 16 03:56:44 CET 2009
Yes thank you I completely agree. A stash of sieves, plus data mine
this very archive for our earlier work on this topic.
My only suggestion is you include a generator version e.g.:
Using Python 3:
>>> g = Primes()
>>> next(g)
-1
>>> next(g)
2
>>> next(g)
3
>>> next(g)
5
etc.
Generators are cool for any infinite sequence, be it convergent,
divergent, oscillatory, or chaotic (finite too).
That's Conway's thing about -1 being prime, feel free to ignore (or
not -- see link).
Bottom line is I'm encouraging us to have RSA in the final mix for
Portland Public (e.g. LEP High and such), meaning we need:
(a) Miller-Rabin or one of those for highly probably prime numbers
(Jython gives direct access to math.BigInteger.probablePrime woo hoo!
or just use my http://markmail.org/message/v43sry4svsvk5nli -- lots of
help from Tim Peters which I'm still happy about)
and
(b) Euclid's extended algorithm (Guido's for the GCD being non-extended).
EEA has other uses, Diophantine equations, continued fractions... Cut
the Knot a good web site.
In other words, in addition to a sieve, we'd like some callables to
test and return (probable) primes (we're talking hundreds of digits in
RSA world).
Kirby
Da links!
http://www.cut-the-knot.org/blue/extension.shtml
http://www.youtube.com/watch?v=4GxP9EVKCjo (for engineers)
http://mathforum.org/library/drmath/view/54241.html
http://www.informationsuebertragung.ch/indexAlgorithmen.html
http://eprints.iisc.ernet.in/11336/
http://mathforum.org/kb/message.jspa?messageID=1093178&tstart=0 (conway.primes)
http://mlblog.osdir.com/python.education/2002-08/msg00084.shtml
(clever marketing)
http://java.sun.com/j2se/1.4.2/docs/api/java/math/BigInteger.html#probablePrime(int,%20java.util.Random)
On Thu, Jan 15, 2009 at 5:33 PM, Gregor Lingl <gregor.lingl at aon.at> wrote:
> I'd like to suggest, that some sort of sieve could be included,
> for instance as a non very fancy example something like
>
> def primes(n):
> s = set(range(3,n+1,2))
> if n >= 2: s.add(2)
> m=3
> while m * m < n:
> s.difference_update(range(m*m, n+1, 2*m))
> m += 2
> while m not in s: m += 2
> return sorted(s)
>
> (as a starting point), or something similar, a bit beautified or
> perhaps you know some different more concise solution ...
>
> An even more compact albeit slightly slower version would be:
>
> def primes(n):
> s = set(range(3,n+1,2))
> for m in range(3, int(n**.5)+1, 2):
> s.difference_update(range(m*m, n+1, 2*m))
> return [2]*(2<=n) + sorted(s)
>
> Or something in between.
> These are imho nice applications of the set type.
>
> Gregor
>
>
>
>
> kirby urner schrieb:
>>
>> Yes, note that my Pascal's includes it, with an embedded zip. Another
>> place list comprehension comes up is in our naive definition of totatives
>> as:
>>
>> def totative(n):
>> return [ t for t in range(1, n) if gcd(t, n) == 1]
>>
>> i.e. all 0 < t < n such that (t, n) have no factors in common (are
>> relatively prime). Then our totient function is simply the len of this
>> list, giving us a quick way to assert (test) Euler's theorem: b **
>> totient(d) % d == 1 where gcd(b,d)==1. There's an easy enough proof in
>> 'Number' by Midhat Gazale, a must have on our syllabus (I'm suggesting).
>>
>> Kirby
>>
>>
>> On Thu, Jan 15, 2009 at 6:35 AM, michel paul <mpaul213 at gmail.com
>> <mailto:mpaul213 at gmail.com>> wrote:
>>
>> I like this.
>>
>> I think another 'must include' for math classes would be list
>> comprehension syntax. Not an algorithm in itself, but an
>> important way of thinking. It's what we try to get them to do
>> using set notation, but in math classes it seems simply like a
>> formality for describing domains, nothing more. In Python, it
>> DOES stuff.
>>
>> - Michel
>>
>> 2009/1/14 kirby urner <kirby.urner at gmail.com
>> <mailto:kirby.urner at gmail.com>>
>>
>> Candidates:
>>
>> "Must include" would be like an intersection of many sets in a
>> Venn Diagram, where we all gave our favorite movies and a very
>> few, such as 'Bagdad Cafe' or 'Wendy and Lucy' or... proved
>> common to us all (no suggesting those'd be -- just personal
>> favorites).
>>
>> In this category, three candidates come to mind right away:
>>
>> Guido's for the gcd:
>>
>> def gcd(a,b):
>> while b:
>> a, b = b, a % b
>> return a
>>
>> Then two generics we've all seen many times, generators for
>> Pascal's Triangle and Fibonacci Sequence respectively:
>>
>> def pascal():
>> """
>> Pascal's Triangle **
>> """
>> row = [1]
>> while True:
>> yield row
>> row = [ a + b for a, b in zip( [0] + row, row + [0] ) ]
>>
>> and:
>>
>> def fibonacci(a=0, b=1):
>> while True:
>> yield a
>> a, b = a + b, a
>>
>> IDLE 1.2.1 >>> from first_steps import *
>> >>> gcd(51, 34)
>> 17
>> >>> g = pascal()
>> >>> g.next()
>> [1]
>> >>> g.next()
>> [1, 1]
>> >>> g.next()
>> [1, 2, 1]
>> >>> g.next()
>> [1, 3, 3, 1]
>> >>> f = fibonacci()
>> >>> f.next()
>> 0
>> >>> f.next()
>> 1
>> >>> f.next()
>> 1
>> >>> f.next()
>> 2
>> >>> f.next()
>> 3
>> >>> f.next()
>> 5
>>
>> Check 'em out in kid-friendly Akbar font (derives from Matt
>> Groening of Simpsons fame):
>> http://www.wobblymusic.com/groening/akbar.html
>>
>> http://www.flickr.com/photos/17157315@N00/3197681869/sizes/o/
>>
>> ( feel free to link or embed in your gnu math website )
>>
>> I'm not claiming these are the only ways to write these. I do
>> think it's a feature, not a bug, that I'm eschewing recursion
>> in all three. Will get to that later, maybe in Scheme just
>> like the Scheme folks would prefer (big lambda instead of
>> little, which latter I saw put to good use at PPUG last night,
>> well attended (about 30)).
>>
>> http://mybizmo.blogspot.com/2009/01/ppug-2009113.html
>>
>> Rationale:
>>
>> In terms of curriculum, these belong together for a host of
>> reasons, not just that we want students to use generators to
>> explore On-Line Encyclopedia of Integer Sequences type
>> sequences. Pascal's Triangle actually contains Fibonaccis
>> along successive diagonals but more important we're laying the
>> foundation for figurate and polyhedral ball packings ala The
>> Book of Numbers, Synergetics, other late 20th century
>> distillations (of math and philosophy respectively).
>> Fibonaccis converge to Phi i.e. (1 + math.sqrt(5) )/2. gcd
>> will be critical in our relative primality checks, leading up
>> to Euler's Theorem thence RSA, per the review below (a
>> literature search from my cube at CubeSpace on Grand Ave):
>>
>> http://cubespacepdx.com/
>> http://mathforum.org/kb/thread.jspa?threadID=1885121&tstart=0
>> <http://mathforum.org/kb/thread.jspa?threadID=1885121&tstart=0>
>> http://www.flickr.com/photos/17157315@N00/3195148912/
>>
>> Remember, every browser has SSL, using RSA for handshaking, so
>> it's not like we're giving them irrelevant info. Number
>> theory goes into every DirecTV box thanks to NDS, other
>> companies making use of this powerful public method.^^
>>
>> You should understand, as a supermarket manager or museum
>> administrator, something about encryption, security, what's
>> tough to the crack and what's not. The battle to make RSA
>> public property was hard won, so it's not like our public
>> school system is eager to surrender it back to obscurity.
>> Student geek wannabes perk up at the thought of getting how
>> this works, not hard to show in Javascript and/or Python.
>> Makes school more interesting, to be getting the low-down.
>>
>> By the same token, corporate trainers not having the luxury of
>> doing the whole nine yards in our revamped grades 8-12, have
>> the ability to excerpt specific juicy parts for the walk of
>> life they're in.
>> Our maths have a biological flavor, thanks to Spore, thanks to
>> Sims. We do a Biotum class almost right away ("Hello World"
>> is maybe part of it's __repr__ ?). I'm definitely tilting
>> this towards the health professions, just as I did our First
>> Person Physics campaign (Dr. Bob Fuller or leader, University
>> of Nebraska emeritus).
>>
>> The reason for using bizarre charactersets in the group theory
>> piece is we want to get their attention off numbers and onto
>> something more generic, could be pictograms, icons, pictures
>> of vegetables...
>>
>> Feedback welcome,
>>
>> Kirby
>>
>>
>> ** http://www.flickr.com/photos/17157315@N00/3198473850/sizes/l/
>> ^^
>>
>> http://www.allbusiness.com/media-telecommunications/telecommunications/5923555-1.html
>>
>>
>> _______________________________________________
>> Edu-sig mailing list
>> Edu-sig at python.org <mailto:Edu-sig at python.org>
>> http://mail.python.org/mailman/listinfo/edu-sig
>>
>>
>>
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> Edu-sig mailing list
>> Edu-sig at python.org
>> http://mail.python.org/mailman/listinfo/edu-sig
>>
>
More information about the Edu-sig
mailing list