Re: [Edu-sig] Pythonic Math must include...

[kirby urner]

On Sun, May 24, 2009 at 8:01 PM, Daniel Ajoy  wrote:

> I've some other candidates that I have included in my Logo Functional
> Extensions (LogoFE).
>
> * A function that receives a math function and plots it.
> * A function that receives a math equation and an interval and finds a root
> in that interval
> * A function that receives a math function and an interval and calculates
> the area under that curve
> * The Ruffini algorithm
> * A function that receives a math function and a X coordinate and finds the
> derivative at that point. Or returns the derivative function if you like.
>
> * Set arithmetic. Including set product. This, together with "join" and
> list comprehensions is all you need instead of SQL
>
> * Functions that produce permutations and combinations of a tuple.
>
>
> Daniel
>
>

All excellent.

One reflex is to "jump to" and start contributing examples, ala PyWhip.

Another reflex is just to agree with the other pros on this list, that we've
got a great list, and then suggest anyone working to cut teeth, in
mathematics not just computer languages, try their hand at at least a few of
these, if not all of them.

On the subject of permutations, I was just happening to share Python with a
noob recently, not that unusual, and wrote the following, which we all know
is "not efficient" and yet conceptually fun, and we cut ourselves slack
here, like what's a few microseconds or even seconds.

If the thing blows up, we know how to kill it.

So what I'm doing in the snippet below is "stuffing a stocking" with all
permutations of 'A', 'B', 'C', 'D' or "four pool balls" (imagine using all
15: 1 + 2 + 3 + 4 + 5:
http://images.google.com/images?hl=en&q=pool+balls+triangle

using the technique of repeated shuffling and using the "set" data structure
(one among many in this philosophy) to screen out the dupes.

We already know the expected number (not cheating, no), so use this code
merely to get the list, which I should bother to sort in the end...  is this
the "best way to do it"?  Might be, if you're wanting to work with the
random module for awhile, do some of those Pascal's Triangle things with the
bell curve and so on.  I left in the error about "hashable" as we're
definitely in MD5 territory etc. i.e. unique mapping indexes, auto-generated
from the content, small chance of collision).

No need to turn up one's nose at "brute force" at every turn, as this new
meaning, involving delicate silicon, is hardly that brutish (IMO).

"""
IDLE 1.2.1
>>> from random import shuffle
>>> emptyset = set()
>>> thecombo = ['A','B','C','D']
>>> # number of sorts:  4*3*2*1 == 24
>>> bagosorts = set()
>>> shuffle(thecombo)
>>> thecombo
['B', 'C', 'D', 'A']
>>> len(bagosorts)
0
>>> while len(bagosorts) < 24:
   bagosorts.add(thecombo)
   shuffle(thecombo)



Traceback (most recent call last):
 File "", line 2, in 
   bagosorts.add(thecombo)
TypeError: list objects are unhashable
>>> # shit!
>>> while len(bagosorts) < 24:
   bagosorts.add(tuple(thecombo))
   shuffle(thecombo)


>>> len(bagosorts)
24
>>> print bagosorts
set([('B', 'A', 'D', 'C'), ('A', 'D', 'B', 'C'), ('A', 'C', 'D', 'B'),
('B', 'C', 'D', 'A'), ('B', 'D', 'C', 'A'), ('C', 'D', 'B', 'A'),
('C', 'A', 'B', 'D'), ('D', 'B', 'A', 'C'), ('B', 'A', 'C', 'D'),
('A', 'D', 'C', 'B'), ('D', 'C', 'A', 'B'), ('C', 'A', 'D', 'B'),
('C', 'B', 'A', 'D'), ('D', 'A', 'B', 'C'), ('A', 'B', 'D', 'C'),
('D', 'C', 'B', 'A'), ('C', 'B', 'D', 'A'), ('A', 'B', 'C', 'D'),
('B', 'D', 'A', 'C'), ('B', 'C', 'A', 'D'), ('D', 'B', 'C', 'A'),
('D', 'A', 'C', 'B'), ('A', 'C', 'B', 'D'), ('C', 'D', 'A', 'B')])


"""


Kirby
___
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig

Re: [Edu-sig] Pythonic Math must include...

[Daniel Ajoy]

I've some other candidates that I have included in my Logo Functional 
Extensions (LogoFE).

* A function that receives a math function and plots it.
* A function that receives a math equation and an interval and finds a root in 
that interval
* A function that receives a math function and an interval and calculates the 
area under that curve
* The Ruffini algorithm
* A function that receives a math function and a X coordinate and finds the 
derivative at that point. Or returns the derivative function if you like.

* Set arithmetic. Including set product. This, together with "join" and list 
comprehensions is all you need instead of SQL

* Functions that produce permutations and combinations of a tuple.


Daniel


___
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig

Re: [Edu-sig] Pythonic Math must include...

[kirby urner]

On Sun, Jan 18, 2009 at 3:31 PM, Gregor Lingl  wrote:

<< SNIP >>

> Of course there are many more possibilities to realize this, for
> instance to use slice-assignment instead of sets. This would
> require some somewhat opaque index calculations, but be - as far
> as I rember - even faster. Particularly I suppose that there
> exist faster algorithms for generating primes, but I admittedly
> don't know them.
>
> ==
>
> Summing up:
>
> Kirby  1.71 s  42.72 s
> Michel Paul1.58 s  32.25 s
> Michel Paul modified:: 0.14 s   1.05 s
> Scott Daniels: 0.07 s   0.50 s
> G.L. minimal sieve:0.014 s  0.109 s
> G.L. sieve:0.012 s  0.086 s
> G.L. sieve-based generator:0.023 s  0.113 s
> (performance depends on CHUNKSIZE)
>
> This exposes in my opinion an unsurmountable dilemma, namely
> that usually you cannot meet even those few criteria mentioned
> in the beginning in a single solution.
> So under the aspects you exposed at the beginning of this thread,
> "Pythonic Math", which title in some sense includes and/or addresses
> this dilemma, how would you prefer to weight those criteria?
>
> Regards
>
> Gregor

Hey Gregor, I'm really pleased you would do some careful analysis
regarding efficiency, one of the several criteria you mentioned.

I do think it's important to look at mathematics as an energetic, ergo
economic, activity, in the sense of consuming clock cycles while
burning through joules, calories (Roz Savage is one of my "action
figures" in my curriculum writing, burning joules as she rows the
Atlantic).  First Person Physics is likewise focused in athletics,
stress medicine.

An inefficient algorithm may well cost you, eat into your free time,
when you could be cutting yourself slack by putting a little more
thought into your technique.  Efficiency matters.  Sometimes we say
"the math is bad" because it's just too dang slow, even if correct
(years too late).  You want a reasoning process able to keep up with
the demands of the day.

So, again, agreeing with you, efficiency is a critical parameter
(interesting conversations with my colleague Trevor Blake on precisely
this point at FG the other day (FG of Fine Grind Productions,
undertaken with Jody Francis (cns.cfo)).

On the other hand, if we're really trying to be blindingly fast, why
are we using Python at all?  Answer:  we're not really trying to be as
fast as possible.

We're more like this:
http://www.istockphoto.com/file_thumbview_approve/422526/2/istockphoto_422526_slug_race.jpg

Speed of execution must not be what matters most.  We're avoiding
cluttering our code with type declarations (yay).  We're indulging in
clean syntax, no curly braces.  We're learning something
cross-platform, respected by industry.

Which is why we're *not* using VBA-per-Access or VB# (smile).

Trial by division is just one of those generic topics the pre-computer
mathematicians would dwell upon, in contrast to the sieve, not that
they're unrelated.

Given we're quite young, just learning about composite versus prime,
starting to get our feet wet in algebra, which is more abstract this
time around, thanks to operator overloading, thanks to "modulo
numbers", we have more of an interest in the timeline, the chronology.
 How have people tackled this problem, of getting prime numbers of
arbitrary size.  Why do we call them "probable primes" in that Jython
method?

By the way, here's a class, adapted from my trial-by-division
generator, that saves state in object variables, and so doesn't need
to be written with yield.

class Primes():

def __init__(self):
self.sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway
self.counter = 0
self.maxprime = 3

def __next__(self):
if self.counter < 3:
self.counter = self.counter + 1
return self.sofar[self.counter - 1]
candidate = self.maxprime + 2 # we'll increment from here on
while True:
for factor in self.sofar[1:]: # skip -1 (or don't use it
in the first place)
if factor ** 2 > candidate:  # did we pass?
self.sofar.append(candidate) # keep the gold
self.maxprime = candidate
self.counter += 1
return candidate # woo hoo!
if not candidate % factor: # oops, no remainder
break  # this is a composite
candidate += 2 # next odd number please

In action, this looks a lot like a generator, except we're also using
numeric indexing to retrieve any prime so far, a new wrinkle:

>>> from trialbydivision import Primes
>>> g = Primes()
>>> next(g)
-1
>>> next(g)
2
>>> next(g)
3
>>> next(g)
5
>>> next(g)
7
>>> next(g)
11
>>> next(g)
13
>>> next(g)
17

Re: [Edu-sig] Pythonic Math must include...

[michel paul]

On Sun, Jan 18, 2009 at 6:11 PM, Gregor Lingl  wrote:

> This exposes in my opinion an unsurmountable dilemma, namely
> that usually you cannot meet even those few criteria mentioned
> in the beginning in a single solution.


I think it's OK that there's not a 'single' solution.  If I saw math
students interested in coming up with their own ways to generate primes,
even if not optimized, wow, I'd be thrilled.

I gave my math students the opportunity to do end of semester projects using
either Python or GeoGebra .  One kid emailed
me saying he had figured out a way to generate any number of rows of
Pascal's triangle using Python, and he wanted to know if this would be an OK
kind of project.  I found that really interesting given the topics in this
thread occurring simultaneously.  I replied to him "Absolutely!"  I haven't
seen his code yet, but I'm really glad that this is what he wanted to
explore.
___
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig

Re: [Edu-sig] Pythonic Math must include...

[Gregor Lingl]

This is a corrected version of my previous posting.

(1) According to the complaint of Michel I have inserted *his*
code instead of Kirby's, which ocurred there (for a second time).
(2) According to a suggestion of Andre I've added (towards the end
of the posting) the code form the cookbook, which is ingenious
but not the fastest one.
(3) I've updated the table of the timings.

Regards, Gregor

kirby urner schrieb:

I think you're correct that the sieve best works with a pre-specified
finite domain:   




To continue work in this area one (or at least me) has to have
some criteria to judge the solutions.
Clearly it was advantageous if there was some consensus about
these criteria in the community.



Fortunately, we have hundreds of years of math pedagogy, so in terms
of avoiding quarrels, start with what's already on the books are "must
have" and just render it Pythonically.




There should be some criteria concerning
(a) the choice of problems and themes,
   e.g. to prefer small problems that expose a single idea  -  or 
rather not

...   etc.,
as well as some
(b) code related criteria, like clarity, conciseness, efficiency, 
beauty (!)

etc., ranked according to
their priorities.



This will be up to each professional teacher in whatever walk of life
-- to judge what to include and what to exclude.  Each teacher will
find her or himself in agreement with some, disagreement with others,
over what to include.  Twas ever thus.
  


I think it's not that easy. I'd like to dive a bit into this topic, 
resuming the code examples
given in this thread and adding a few additional ideas. What concerns 
efficiency, I've
measured the time to compute the 9592/9593 primes in the range up to 
10 and (in order to
get some idea how the algorithm scales) also those up to 50 (on my 
machine).


Here is your, Kirby's, code:

def primes():
  sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway
  yield sofar[0] # get these out of the way
  yield sofar[1] # the only even prime
  yield sofar[2] # and then 3
  candidate = 5 # we'll increment from here on
  while True: # go forever
  for factor in sofar[1:]: # skip -1 (or don't use it in the first 
place)

  if factor ** 2 > candidate:  # did we pass?
  yield candidate # woo hoo!
  sofar.append(candidate) # keep the gold
  break  # onward!
  if not candidate % factor: # oops, no remainder
  break  # this is a composite
  candidate += 2 # next odd number please

Time:10:  1.71 s50:  42.72 s
-

Michel Paul's code:

def primes():
   p = [-1, 2, 3]
   for x in p: yield x
   def is_prime(n):
   for factor in p[1:]:
   if factor**2 > n: return True
   if n%factor == 0: return False
   multiple = 6
   while True:
   if is_prime(multiple-1): yield multiple-1; p.append(multiple-1)
   if is_prime(multiple+1): yield multiple + 1; p.append(multiple+1)
   multiple += 6


Time:10:  1.58 s50:  32.25 s
-

I've modified this one slightly, with a surprising effect
(I conjecture mainly due to avoiding copying p repeatedly):

def primes():
  yield(-1)
  p = [2, 3]
  for x in p: yield x
  def is_prime(n):
  for factor in p:
  if factor**2 > n: return True
  if n%factor == 0: return False
  multiple = 6
  while True:
  for cand in multiple-1, multiple+1:
  if is_prime(cand):
  yield cand
  p.append(cand)
  multiple += 6

Time:10:  0.14 s50:  1.05 s
-

Scott Daniels code:

def primes():
  for x in -1, 2, 3:
  yield x
  gen = primes().next
  for top in iter(gen, 3):
  pass # skip useless tests (we skip all multiples of 2 or 3)
  factors = []
  # get pump ready for a 5
  check = -1
  limit = 3 * 3 - 2 # How far will 3 work as top prime?
  factors = []
  while True:
  check += 6
  if check >= limit: # move if this pair needs another factor
  top = gen()
  limit = top * top - 2 # limit for both candidates
  factors.append(top)
  for element in check, check + 2:
  for factor in factors:
  if element % factor == 0:
  break
  else:
  yield element

Time:10:  0.07 s50:  0.50 s
-

Compare the above generators to sieve algorithms:

G.L. minimal sieve

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)

Time:10:  0.014 s50:  0.11 s
-


G.L.: sieve

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)

Time:10:  0.012 s50:  0.086 s
-

Apparently sieves are considerably faster at

Re: [Edu-sig] Pythonic Math must include...

[Gregor Lingl]

michel paul schrieb:
On Sun, Jan 18, 2009 at 3:31 PM, Gregor Lingl > wrote:
 


Michel Paul's code:


def primes():
  sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway
  yield sofar[0] # get these out of the way
  yield sofar[1] # the only even prime
  yield sofar[2] # and then 3
  candidate = 5 # we'll increment from here on
  while True: # go forever
  for factor in sofar[1:]: # skip -1 (or don't use it in the
first place)
  if factor ** 2 > candidate:  # did we pass?
  yield candidate # woo hoo!
  sofar.append(candidate) # keep the gold
  break  # onward!
  if not candidate % factor: # oops, no remainder
  break  # this is a composite
  candidate += 2 # next odd number please

Time:10:  1.58 s50:  32.25 s
-


Actually, that's Kirby's code.
This is what I sent:

def primes():
p = [-1, 2, 3]
for x in p: yield x
def is_prime(n):
for factor in p[1:]:
if factor**2 > n: return True
if n%factor == 0: return False
multiple = 6
while True:
if is_prime(multiple-1): yield multiple-1; p.append(multiple-1)
if is_prime(multiple+1): yield multiple + 1; p.append(multiple+1)
multiple += 6

Is this what was tested?  Or what was listed?  Just curious.

Sorry. Of course, you are right. That was a copy and paste - error.
Your code was what was tested and the result of which is listed in
the table. And you can easily recognize, that it was also your code,
that I had modified. (see below)

Next time I'll be more careful

Gregor

 


I've modified this one slightly, with a surprising effect
(I conjecture mainly due to avoiding copying p repeatedly):

def primes():
  yield(-1)
  p = [2, 3]

  for x in p: yield x
  def is_prime(n):
  for factor in p:

  if factor**2 > n: return True
  if n%factor == 0: return False
  multiple = 6
  while True:
  for cand in multiple-1, multiple+1:
  if is_prime(cand):
  yield cand
  p.append(cand)
  multiple += 6

Time:10:  0.14 s50:  1.05 s
-


Yeah, I like the 'for cand in multiple-1, multiple+1'.  I actually did 
do it that way on a previous occasion.  So this is very interesting.


- Michel

___
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig

Re: [Edu-sig] Pythonic Math must include...

[michel paul]

On Sun, Jan 18, 2009 at 3:31 PM, Gregor Lingl  wrote:


> Michel Paul's code:
>
> def primes():
>   sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway
>   yield sofar[0] # get these out of the way
>   yield sofar[1] # the only even prime
>   yield sofar[2] # and then 3
>   candidate = 5 # we'll increment from here on
>   while True: # go forever
>   for factor in sofar[1:]: # skip -1 (or don't use it in the first
> place)
>   if factor ** 2 > candidate:  # did we pass?
>   yield candidate # woo hoo!
>   sofar.append(candidate) # keep the gold
>   break  # onward!
>   if not candidate % factor: # oops, no remainder
>   break  # this is a composite
>   candidate += 2 # next odd number please
>
> Time:10:  1.58 s50:  32.25 s
> -


Actually, that's Kirby's code.
This is what I sent:

def primes():
p = [-1, 2, 3]
for x in p: yield x
def is_prime(n):
for factor in p[1:]:
if factor**2 > n: return True
if n%factor == 0: return False
multiple = 6
while True:
if is_prime(multiple-1): yield multiple-1; p.append(multiple-1)
if is_prime(multiple+1): yield multiple + 1; p.append(multiple+1)
multiple += 6

Is this what was tested?  Or what was listed?  Just curious.


> I've modified this one slightly, with a surprising effect
> (I conjecture mainly due to avoiding copying p repeatedly):
>
> def primes():
>   yield(-1)
>   p = [2, 3]
>   for x in p: yield x
>   def is_prime(n):
>   for factor in p:
>   if factor**2 > n: return True
>   if n%factor == 0: return False
>   multiple = 6
>   while True:
>   for cand in multiple-1, multiple+1:
>   if is_prime(cand):
>   yield cand
>   p.append(cand)
>   multiple += 6
>
> Time:10:  0.14 s50:  1.05 s
> -
>
>
Yeah, I like the 'for cand in multiple-1, multiple+1'.  I actually did do it
that way on a previous occasion.  So this is very interesting.

- Michel
___
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig

Re: [Edu-sig] Pythonic Math must include...

[Andre Roberge]

On Sun, Jan 18, 2009 at 7:31 PM, Gregor Lingl  wrote:
[SNIP]

> ==
>
> Summing up:
>
> Kirby  1.71 s  42.72 s
> Michel Paul1.58 s  32.25 s
> Michel Paul modified:: 0.14 s   1.05 s
> Scott Daniels: 0.07 s   0.50 s
> G.L. minimal sieve:0.014 s  0.109 s
> G.L. sieve:0.012 s  0.086 s
> G.L. sieve-based generator:0.023 s  0.113 s
> (performance depends on CHUNKSIZE)
>

You may also want to consider the following:

'''
Sieve of erathosthenes, from the Python Cookbook, 2nd edition

'''

import itertools
import pprint

def erathosthenes():
'''Yields the sequence of prime numbers via the Sieve of Erathosthenes.'''
D = {}  # map each composite integer to its first-found prime factor
for q in itertools.count(2): # q gets 2, 3, 4, 5, ... ad infinitum
p = D.pop(q, None)
if p is None:
# q not a key in D, so q is a prime, therefore, yield it
yield q
# mark q square as not-prime (with q as first found prime factor)
D[q*q] = q
if __name__ == '__main__':
pprint.pprint(D)
else:
# q is a composite number with p as its first-found prime number
# So, let's try to find the next smallest possible composite to
# add and that was not already present with the same first-found
# prime number
x = q + p
while x in D:
x += p
D[x] = p

if __name__ == '__main__':
sieve = erathosthenes()
for i in range(10):
print sieve.next()



===
André
___
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig

Re: [Edu-sig] Pythonic Math must include...

[Gregor Lingl]

kirby urner schrieb:

I think you're correct that the sieve best works with a pre-specified
finite domain: 
  




To continue work in this area one (or at least me) has to have
some criteria to judge the solutions.
Clearly it was advantageous if there was some consensus about
these criteria in the community.



Fortunately, we have hundreds of years of math pedagogy, so in terms
of avoiding quarrels, start with what's already on the books are "must
have" and just render it Pythonically.




There should be some criteria concerning
(a) the choice of problems and themes,
   e.g. to prefer small problems that expose a single idea  -  or rather not
...   etc.,
as well as some
(b) code related criteria, like clarity, conciseness, efficiency, beauty (!)
etc., ranked according to
their priorities.



This will be up to each professional teacher in whatever walk of life
-- to judge what to include and what to exclude.  Each teacher will
find her or himself in agreement with some, disagreement with others,
over what to include.  Twas ever thus.
  


I think it's not that easy. I'd like to dive a bit into this topic, 
resuming the code examples
given in this thread and adding a few additional ideas. What concerns 
efficiency, I've
measured the time to compute the 9592/9593 primes in the range up to 
10 and (in order to
get some idea how the algorithm scales) also those up to 50 (on my 
machine).


Here is your, Kirby's, code:

def primes():
   sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway
   yield sofar[0] # get these out of the way
   yield sofar[1] # the only even prime
   yield sofar[2] # and then 3
   candidate = 5 # we'll increment from here on
   while True: # go forever
   for factor in sofar[1:]: # skip -1 (or don't use it in the first 
place)

   if factor ** 2 > candidate:  # did we pass?
   yield candidate # woo hoo!
   sofar.append(candidate) # keep the gold
   break  # onward!
   if not candidate % factor: # oops, no remainder
   break  # this is a composite
   candidate += 2 # next odd number please

Time:10:  1.71 s50:  42.72 s
-

Michel Paul's code:

def primes():
   sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway
   yield sofar[0] # get these out of the way
   yield sofar[1] # the only even prime
   yield sofar[2] # and then 3
   candidate = 5 # we'll increment from here on
   while True: # go forever
   for factor in sofar[1:]: # skip -1 (or don't use it in the first 
place)

   if factor ** 2 > candidate:  # did we pass?
   yield candidate # woo hoo!
   sofar.append(candidate) # keep the gold
   break  # onward!
   if not candidate % factor: # oops, no remainder
   break  # this is a composite
   candidate += 2 # next odd number please

Time:10:  1.58 s50:  32.25 s
-

I've modified this one slightly, with a surprising effect
(I conjecture mainly due to avoiding copying p repeatedly):

def primes():
   yield(-1)
   p = [2, 3]
   for x in p: yield x
   def is_prime(n):
   for factor in p:
   if factor**2 > n: return True
   if n%factor == 0: return False
   multiple = 6
   while True:
   for cand in multiple-1, multiple+1:
   if is_prime(cand):
   yield cand
   p.append(cand)
   multiple += 6

Time:10:  0.14 s50:  1.05 s
-

Scott Daniels code:

def primes():
   for x in -1, 2, 3:
   yield x
   gen = primes().next
   for top in iter(gen, 3):
   pass # skip useless tests (we skip all multiples of 2 or 3)
   factors = []
   # get pump ready for a 5
   check = -1
   limit = 3 * 3 - 2 # How far will 3 work as top prime?
   factors = []
   while True:
   check += 6
   if check >= limit: # move if this pair needs another factor
   top = gen()
   limit = top * top - 2 # limit for both candidates
   factors.append(top)
   for element in check, check + 2:
   for factor in factors:
   if element % factor == 0:
   break
   else:
   yield element

Time:10:  0.07 s50:  0.50 s
-

Compare the above generators to sieve algorithms:

G.L. minimal sieve

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)

Time:10:  0.014 s50:  0.11 s
-


G.L.: sieve

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)

Time:10:  0.012 s50:  0.086 s
-

Apparently sieves are considerably faster at the cost
that the whole sieve has

Re: [Edu-sig] Pythonic Math must include...

[Scott David Daniels]

michel paul wrote:
... An interesting fact is that, except for 2 and 3, all primes are adjacent 
to a multiple of 6

Having once been interested in prime pairs, I remember having written
a lot of code based on this "back in the day."  Here is my version of
your generator:

def primes():
for x in -1, 2, 3:
yield x
gen = primes().next
for top in iter(gen, 3):
pass # skip useless tests (we skip all multiples of 2 or 3)
factors = []
# get pump ready for a 5
check = -1
limit = 3 * 3 - 2 # How far will 3 work as top prime?
factors = []
while True:
check += 6
if check >= limit: # move if this pair needs another factor
top = gen()
limit = top * top - 2 # limit for both candidates
factors.append(top)
for element in check, check + 2:
for factor in factors:
if element % factor == 0:
break
else:
yield element

--Scott David Daniels
scott.dani...@acm.org

___
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig

Re: [Edu-sig] Pythonic Math must include...

[kirby urner]

On Sat, Jan 17, 2009 at 11:59 PM, michel paul  wrote:
> I definitely believe that a good way to improve our current math curriculum
> would be to weave in computational number theory.  This would be the 21st
> century answer to 'back to basics'.
>

Yes.  OSCON avatar R0ml has puts a strong liberal arts spin, says
these language games with computers are the new rhetoric, the basis
for responsible civic participation.

If they deny you access to these skills, that's a clear conspiracy to
disempower you, or feel free to treat it that way:  blend in, act like
nothing is wrong, then network with your friends like crazy after
school, do peer to peer teaching.  Bone up on what they're
withholding, your right as a citizen.

Fortunately, Portland makes that easy, what with OS Bridge, Saturday
Academy and so on.  Plus some of our public schools have already
turned the corner.  LEP High is all open source Ubuntu on wireless,
had me in peer teaching Python years ago by now (realized they could
do it).

> I think a huge problem in student math illiteracy has to do with not
> understanding division, remainders, and ratios.  When dealing with division,
> our curriculum tends to focus on quotients, but understanding the nature of
> the remainder has a lot to do with what math and technology are about these
> days.
>

Per our Shuttleworth meetup in London that time (some years ago), in
South Africa at least they're just bored out of their skulls if you
didn't share the cool toys with them (the students).  "When do we get
to learn about computers?  That's what we're here for.  We know this
knowledge is necessary to run companies, governments, any large scale
service.  If that's not what we're learning, why are we here?"
Tuxlabs, Freedom Toasters, OLPC... all pieces of the puzzle.

Many (not all) North Americans are more docile and controllable,
weren't oppressed by years of apartheid, and so take it sitting down
when you say you're "teaching math" but teach nothing about the
executable math notations except on a TI (very anemic and
underpowered, a joke if you're trying to run a railroad).

> Exploring how to find primes is definitely a 'must include' in a
> computational math curriculum.  I think students should explore this in a
> variety of ways, including both sieves and generators, discussing why one
> might choose one approach or another in various situations.  This would do a
> whole lot of good for both math and tech literacy simultaneously.

Yes, and the literature is already well developed.  The Fermat Test
works pretty well actually.  If 2**(p-1) % p is 1, you're likely
dealing with a prime.  Let's test it:

>>> sequence = fermat_test()
>>> next(sequence)
5
>>> next(sequence)
7
>>> next(sequence)
11
>>> next(sequence)
13
>>> next(sequence)
17
>>> next(sequence)
19
>>> next(sequence)
23
>>> next(sequence)
29
>>> next(sequence)
31

Pretty good huh.  If you hard code the exceptions (as a list) you can
get a long way with this.  It's also a good lesson in simple logic:
"IF you're a prime THEN you will pass the Fermat Test" is true, but
"IF you pass the Fermat Test THEN you are prime" is false.  Talk about
Carmichael Numbers.

The Fermat Test is based on Euler's Theorem that a base to a totient
power of N, mod N, nets you unity.

RSA encrypts your message m by raising it to a 3rd power (say) mod
public key i.e. c = pow(m, 3, N), but then we know the inverse of 3,
call it d, mod totient(N) such that pow(c, d, N) will be the base
itself, i.e. m (we've gone "around the clock" just the right
distance).

d is kept secret to the receiver, N is published and used to encrypt
by the sender (as is the source code, patent expired).  Unless you
know totient(N) you're unable to crack c, but that requires knowing
the two prime factors of N, which got thrown away.  totient(N) =
(p-1)*(q-1).

Example:
N = 17 * 23
totN = 16 * 22
m = 111
Go c = pow(111, 3, N)
get d such that 3*d % totN == 1

Brute force why not:

>>> for i in range(1, totN):
if (3*i) % totN == 1:
print(i)


235

get m back:

>>> c
304
>>> (3 * d) % totN
1
>>> pow(c, d, N)
111

Ta da!

In SSL, you don't need any published N, can establish that upon
handshaking.  If you want your email encrypted, then publish your N.

Thanks to our early group theory exercises (e.g. Vegetable Group
Soup), our South Africans, North Americans or whatever, know "inverse"
means something vis-a-vis a multiplicative identity, i.e. 1 or unity.
These "modulo numbers" (as we call them), may be defined as a simple
Python class and made to spit out their tables, including their power
tables.

We override __mul__ to get these, study group properties of Closure,
Associativity, Inverse and Neutral element (CAIN).

Even before this, we've used the concept of "relatively prime" to
define totatives and totient.  The whole discussion of primes versus
composites goes into this, which is where we get to these generators.

Miller-Rabin is a strong primality tester, stro

Re: [Edu-sig] Pythonic Math must include...

[michel paul]

I definitely believe that a good way to improve our current math curriculum
would be to weave in computational number theory.  This would be the 21st
century answer to 'back to basics'.

I think a huge problem in student math illiteracy has to do with not
understanding division, remainders, and ratios.  When dealing with division,
our curriculum tends to focus on quotients, but understanding the nature of
the remainder has a lot to do with what math and technology are about these
days.

Exploring how to find primes is definitely a 'must include' in a
computational math curriculum.  I think students should explore this in a
variety of ways, including both sieves and generators, discussing why one
might choose one approach or another in various situations.  This would do a
whole lot of good for both math and tech literacy simultaneously.

An interesting fact is that, except for 2 and 3, all primes are adjacent to
a multiple of 6.  That is easy to prove:

Let n be a multiple of 6.
n+1 might be prime.
n+2 is divisible by 2.
n+3 is divisible by 3.
n+4 is divisible by 2.
n+5 might be prime
n+6 is another multiple of 6.

Here's a generator that uses this jumping by 6 approach:

def primes():
p = [-1, 2, 3]
for x in p: yield x
def is_prime(n):
for factor in p[1:]:
if factor**2 > n: return True
if n%factor == 0: return False
multiple = 6
while True:
if is_prime(multiple-1): yield multiple-1; p.append(multiple-1)
if is_prime(multiple+1): yield multiple + 1; p.append(multiple+1)
multiple += 6

- Michel

On Sat, Jan 17, 2009 at 9:31 PM, kirby urner  wrote:

> On Sat, Jan 17, 2009 at 5:40 PM, Gregor Lingl  wrote:
> >
> >
> > kirby urner schrieb:
> >>
> >> 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.:
> >>
> >
> > At first this seems an attractive idea, but in my opinion the
> > idea of sieves is fairly antagonistic to that of generators.
> > A sieve  is used  to eliminate  from a given set elements
> > that have not some desired property, while generators
> > (ideally) create  objects, one at atime,  with that desired
> > property. Drastically: you cannot sieve at first all even
> > numbers from an infinite set or sequence. For educational
> > purposes I'd prefer examples that display a single concept
> > in a small and simple way. :-*  A prime number generater
> > based on some different algorithm of course may be
> > interesting and useful.
>
> Yes sir!  Excellent clarification.  The goal is to have a worthy
> generator that always gives the next prime.  "Trial by division" is
> the simplest approach I can think of...
>
> >>> def primes():
>sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway
>yield sofar[0] # get these out of the way
>yield sofar[1] # the only even prime
>yield sofar[2] # and then 3
>candidate = 5 # we'll increment from here on
>while True: # go forever
>for factor in sofar[1:]: # skip -1 (or don't use it in the
> first place)
>if factor ** 2 > candidate:  # did we pass?
>yield candidate # woo hoo!
>sofar.append(candidate) # keep the gold
>break  # onward!
>if not candidate % factor: # oops, no remainder
>break  # this is a composite
>candidate += 2 # next odd number please
>
>
> >>> g = primes()
> >>> next(g)
> -1
> >>> next(g)
> 2
> >>> next(g)
> 3
> >>> next(g)
> 5
> >>> next(g)
> 7
> >>> next(g)
> 11
> >>> next(g)
> 13
> >>> next(g)
> 17
> >>> next(g)
> 19
> >>> next(g)
> 23
> >>> next(g)
> 29
> >>> next(g)
> 31
> >>> next(g)
> 37
> >>> next(g)
> 41
>
> I think you're correct that the sieve best works with a pre-specified
> finite domain:  sieve it completely, using divisors <
> math.sqrt(len(domain)) then iterate over it maybe, but the array is
> already populated, taking up memory.  The above generator, in
> contrast, gradually takes up more memory (shows what generators are
> good for then: saving state between cycles).
>
> > To continue work in this area one (or at least me) has to have
> > some criteria to judge the solutions.
> > Clearly it was advantageous if there was some consensus about
> > these criteria in the community.
>
> Fortunately, we have hundreds of years of math pedagogy, so in terms
> of avoiding quarrels, start with what's already on the books are "must
> have" and just render it Pythonically.
>
> So, for example, every pre-college math curriculum I'm aware of makes
> the distinction between prime and composite numbers.
>
> On the other hand, few include the Fermat test or Fermat's Little
> Theorem, don't have RSA as a goal.  So whereas generators for primes,

Re: [Edu-sig] Pythonic Math must include...

[kirby urner]

On Sat, Jan 17, 2009 at 5:40 PM, Gregor Lingl  wrote:
>
>
> kirby urner schrieb:
>>
>> 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.:
>>
>
> At first this seems an attractive idea, but in my opinion the
> idea of sieves is fairly antagonistic to that of generators.
> A sieve  is used  to eliminate  from a given set elements
> that have not some desired property, while generators
> (ideally) create  objects, one at atime,  with that desired
> property. Drastically: you cannot sieve at first all even
> numbers from an infinite set or sequence. For educational
> purposes I'd prefer examples that display a single concept
> in a small and simple way. :-*  A prime number generater
> based on some different algorithm of course may be
> interesting and useful.

Yes sir!  Excellent clarification.  The goal is to have a worthy
generator that always gives the next prime.  "Trial by division" is
the simplest approach I can think of...

>>> def primes():
sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway
yield sofar[0] # get these out of the way
yield sofar[1] # the only even prime
yield sofar[2] # and then 3
candidate = 5 # we'll increment from here on
while True: # go forever
for factor in sofar[1:]: # skip -1 (or don't use it in the 
first place)
if factor ** 2 > candidate:  # did we pass?
yield candidate # woo hoo!
sofar.append(candidate) # keep the gold
break  # onward!
if not candidate % factor: # oops, no remainder
break  # this is a composite
candidate += 2 # next odd number please


>>> g = primes()
>>> next(g)
-1
>>> next(g)
2
>>> next(g)
3
>>> next(g)
5
>>> next(g)
7
>>> next(g)
11
>>> next(g)
13
>>> next(g)
17
>>> next(g)
19
>>> next(g)
23
>>> next(g)
29
>>> next(g)
31
>>> next(g)
37
>>> next(g)
41

I think you're correct that the sieve best works with a pre-specified
finite domain:  sieve it completely, using divisors <
math.sqrt(len(domain)) then iterate over it maybe, but the array is
already populated, taking up memory.  The above generator, in
contrast, gradually takes up more memory (shows what generators are
good for then: saving state between cycles).

> To continue work in this area one (or at least me) has to have
> some criteria to judge the solutions.
> Clearly it was advantageous if there was some consensus about
> these criteria in the community.

Fortunately, we have hundreds of years of math pedagogy, so in terms
of avoiding quarrels, start with what's already on the books are "must
have" and just render it Pythonically.

So, for example, every pre-college math curriculum I'm aware of makes
the distinction between prime and composite numbers.

On the other hand, few include the Fermat test or Fermat's Little
Theorem, don't have RSA as a goal.  So whereas generators for primes,
fibonaccis, pascal's triangle, would seem non-controversial, anything
having to do with Fermat's Little Theorem would seem an uphill battle,
especially without buy in on the RSA bit.

What makes a lot of this stuff more accessible than before is we have
the ability to work with large numbers of digits.  Both text books and
calculators tend to crap out at more that 15 significant figures.  Not
so in Python or any significantly endowed language.  2 ** 1 is no
problem for us, is for the paper and pencil crowd, or the TI crowd
(both pitiable).

I don't think there's a way to avoid quarrels.  People have different
leadings, throw their hats in the ring, and we see what synergies
develop.  My goal is to keep the process open and participatory, not
to close it down.  The sight of people debating is far less disturbing
than the sight of everyone in lockstep (the Borg).

>
> There should be some criteria concerning
> (a) the choice of problems and themes,
>e.g. to prefer small problems that expose a single idea  -  or rather not
> ...   etc.,
> as well as some
> (b) code related criteria, like clarity, conciseness, efficiency, beauty (!)
> etc., ranked according to
> their priorities.

This will be up to each professional teacher in whatever walk of life
-- to judge what to include and what to exclude.  Each teacher will
find her or himself in agreement with some, disagreement with others,
over what to include.  Twas ever thus.

What to avoid, in my book, is a restrictive environment which takes a
one size fits all approach and dictates to all teachers how it must
be, removing much individual freedom.

Reduction in biodiversity is dangerous in my estimation.

That's why I fight against "national curriculum" ideologues on the
Math Forum, other places.

> Once I had the following idea: there are so m

Re: [Edu-sig] Pythonic Math must include...

[Gregor Lingl]

kirby urner schrieb:

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.:
  
At first this seems an attractive idea, but in my opinion the idea of 
sieves is fairly antagonistic
to that of generators.  A sieve  is used  to eliminate  from a given set 
elements that have
not some desired property, while generators  (ideally) create  objects, 
one at atime,  with
that desired property. Drastically: you cannot sieve at first all even 
numbers from an infinite set or
sequence. For educational purposes I'd prefer examples that display a 
single concept in
a small and simple way. :-*  A prime number generater based on some 
different algorithm of

course may be interesting and useful.

To continue work in this area one (or at least me) has to have some 
criteria to judge the solutions.
Clearly it was advantageous if there was some consensus about these 
criteria in the community.


There should be some criteria concerning
(a) the choice of problems and themes,
e.g. to prefer small problems that expose a single idea  -  or 
rather not ...   etc.,

as well as some
(b) code related criteria, like clarity, conciseness, efficiency, beauty 
(!) etc., ranked according to

their priorities.

Once I had the following idea: there are so many renowned pythonistas in 
the developers
community, many of them also interested to promote Python in the 
educational area (see for
instance the protagonists in Jeffrey Elkners "Introducing Python"). How 
about to ask them
to make a personal donation to the educators and learners: a piece of 
code, 10 to 12 lines
at most, that they individually consider  to  show most convincingly the 
power or the beauty
of programming with Python - or the fun they have with it. Young people 
like role models ;-)


Regrettably I didn't persue that idea further. What do you think of it. 
Ok, the days of the

early pioneers are over, but perhaps it's still worth a try?

Regards,
Gregor




   

Using Python 3:

  

g = Primes()
next(g)


-1
  

next(g)



  

___
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig

Re: [Edu-sig] Pythonic Math must include...

[kirby urner]

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

Re: [Edu-sig] Pythonic Math must include...

[Gregor Lingl]

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 > 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 mailto:kirby.ur...@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/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/
   

Re: [Edu-sig] Pythonic Math must include...

[kirby urner]

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

Re: [Edu-sig] Pythonic Math must include...

[michel paul]

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 

> 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://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
> Edu-sig@python.org
> http://mail.python.org/mailman/listinfo/edu-sig
>
>
___
Edu-sig 

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

[kirby urner]

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://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
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig