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 <[email protected]> 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 <[email protected] >> <mailto:[email protected]>> 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 <[email protected] >> <mailto:[email protected]>> >> >> 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/17157...@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/17157...@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/17157...@n00/3198473850/sizes/l/ >> ^^ >> >> >> http://www.allbusiness.com/media-telecommunications/telecommunications/5923555-1.html >> >> >> _______________________________________________ >> Edu-sig mailing list >> [email protected] <mailto:[email protected]> >> http://mail.python.org/mailman/listinfo/edu-sig >> >> >> >> ------------------------------------------------------------------------ >> >> _______________________________________________ >> Edu-sig mailing list >> [email protected] >> http://mail.python.org/mailman/listinfo/edu-sig >> > _______________________________________________ Edu-sig mailing list [email protected] http://mail.python.org/mailman/listinfo/edu-sig
