# [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

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
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

http://www.cut-the-knot.org/blue/extension.shtml
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,
>>
>>        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
>>
>
```