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
