# [Edu-sig] Pythonic Math must include...

Gregor Lingl gregor.lingl at aon.at
Fri Jan 16 02:33:38 CET 2009

```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))
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,
>
>         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://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
>         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
>
>         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/
>         ^^
>
>
>         _______________________________________________
>         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
>
```