'''
                            M A N I F E S T O

                              Michel Paul
                        Beverly Hills High School
                              March, 2008 
~ '''
from __future__ import division
from math import *
'''
Notice the colors! Keywords orange, identifiers black, comments green.

If you DON'T see colorful text here, then either

    you didn't open this in IDLE (Python's IDE from python.org)
    - or -
    you didn't save this with a .py suffix.

Here are some quotes that I find pertinent:

===============================================================================

"It is unworthy of excellent men to lose hours like slaves in the labor of
 calculation which could be safely relegated to anyone else if machines were
 used."
         -- Leibnitz

"Any sufficiently advanced technology is indistinguishable from magic."

        -- Arthur C. Clarke

"It goes against the grain of modern education to teach children to program.
 What fun is there in making plans, acquiring discipline in organizing thoughts,
 devoting attention to detail and learning to be self-critical?

         -- Alan Perlis, Epigrams in Programming "

"Computer Science is no more about the computer than astronomy is about
 the telescope."

        -- Edgar Dykstra

"Computation is the principle; the computer is the tool."

        -- Peter Denning

"Computer science is the new mathematics."

        -- Dr. Christos Papadimitriou

"We ascribe beauty to that which is simple,
 which has no superfluous parts;
 which exactly answers its end,
 which stands related to all things,
 which is the mean of many extremes."

        -- Ralph Waldo Emerson, The Conduct of Life

"You may say I'm a dreamer, but I'm not the only one."

        -- John Lennon

"But when they came to letters, 'This', said Theuth, 'will make the Egyptians
 wiser and give them better memories; it is a specific both for the memory and
 for the wit.'  Thamus replied: 'O most ingenious Theuth, ... this discovery of
 yours will create forgetfulness in the learners' souls, because they will not
 use their memories; they will trust to the external written characters and not
 remember of themselves. The specific which you have discovered is an aid not to
 memory, but to reminiscence...' "

        --Plato, Phaedrus

===============================================================================
    
This presentation is not just about 'Python' per se.  Python is simply an
efficient, elegant and delightful language for exploring a new kind of thinking.

This new way of thinking is often called 'computational' thinking.

This new kind of thinking has a whole lot to do with what mathematics is,
especially these days.

This is not just about 'learning to program', although that is part of it.

This is about 'programming to learn'.

Programming is the art of reducing complexity to a set of primitive operations.

I believe that the debates regarding the use of calculators in the math
classroom were misguided.  These debates were usually framed as being between
'traditionalists' and 'progressives', but there has existed a third perspective
that was seldom considered, and this perspective is closer to the heart of both
contemporary mathematics and technology than either camp ever was in the
'calculator wars'.  This third perspective integrates the concerns of both the
traditionalists and the progressives in a unified and elegant way, and it
reflects what is currently going on in mathematical and scientific research at
the university level.

Instead of debating whether the use of technology provides a 'tool' or becomes a
'crutch', let's discuss the fact that, these days, technology is language.

The art of programming is an essentially mathematical way of thinking, similar
to writing a proof, and THIS is its pedagogical value.

Programming has evolved dramatically over the last couple of decades, and it is
changing how science thinks.  It used to be that the two pillars of science were
theory and experimentation.  There are now three pillars of science - theory,
experimentation, and computational modeling.  This is a fact.  Check it out.
Google it!  It is now possible to get a PhD in Computational Mathematics.

I went to CalTech for a conference a couple of years ago when I first
discovered Python.  Several scientists there said to me, "It's so good that your
school would send you to something like this!"  I just kind of shrugged and
said, "Well, they didn't actually send me.  They don't even know I'm here."  The
message from scientists there was that this thinking needs to become part of the
general curriculum.  They want students to see this stuff early - and NOT just
as CS students!

Many people think of technology as something that programmers create for us,
that programmers should just do their job while we kick back and play with, or
'use', what they have created.  We, the users, shouldn't have to worry about
programming itself, as, after all, that's what 'programmers' get paid to do.

This consumer model is what dominates American K-12 math education.  Why?
This is very unfortunate, as it tends to preclude many important discussions.

In the November 2007 Notices of the American Mathematical Society an opinion
piece was published on the importance of open source mathematical software.  To
many people 'open source' simply means 'free', but there is far more to it than
that.  An important principle of open source software is peer review.  A growing
number of mathematicians these days are criticizing proofs that utilize
proprietary software.  When not everything is open for checking, as is the case
with proprietary software, a fundamental principle of mathematical discourse is
violated.  Open source software is becoming an increasingly important
intellectual resource, and it would be good for students to be made aware of it.

See www.ams.org/notices/200710/tx071001279p.pdf 

The fact that technology these days is a language that is founded on the
concepts of function and object should be of interest to math educators, as
these concepts also have a whole lot to do with what mathematics itself is.

The term 'object' might not seem familiar in a mathematical context, but math
itself has been object-oriented ever since Pythagoras.  Mathematical objects are
things like integers, ratios, points, polygons, circles, polynomials, etc.  They
are virtual objects that have properties we can describe.

"Fractions are objects, not unfinished division problems."

        -- Michel Paul

Many people think of programming as 'getting a machine to do what you want it to
do', and so the suggestion of integrating programming into math classes seems no
more significant than other ways of getting a machine to 'do the math'.

However, programming has evolved into something much more than ordering a
machine to do one's bidding.  Contemporary programming is descriptive rather
than imperative.  It is a way of organizing ideas.

These days a program is not thought of as a set of commands.
Rather, a program is a set of interacting definitions.
This is highly significant for mathematics education.

Funny thing - we often say that 'mathematics is a language', but we really don't
teach it that way.  We pay lip service to the field axioms at the beginning of
the year, but these often fade into the background.

For example, using the 'language' of mathematics,
how would we define 'the factors of n'?

We can list the factors(12) as [1, 2, 3, 4, 6, 12].

We can list the factors(38743) as [1, 17, 43, 53, 731, 901, 2279, 38743].

But, how would we 'list' the factors(n)?

We could use set notation to do this, but it is precisely the kind of thing the
average student would dismiss this with "How am I ever going to USE this?"

Well, let's try expressing it computationally:
~ '''
def factors(n): return [x for x in range(1, n+1) if n%x == 0]
'''
We can read the definition in this way:

    The 'factors of n' is a list containing the numbers x
    ranging from 1 through n for which the remainder of n/x is 0.

Now, what part of this is not algebraic?  NONE of it!!
It is pure Pythonic syntax, sure, but it is also purely algebraic.

This style of expression, known as 'list comprehension', is found in several
contemporary functional languages.  None of the notation used here is beyond
Algebra I, yet it says the same thing we would say using set notation.

This definition efficiently and accurately captures what we mean by 'the factors
of n'.  What's more, you can USE this definition, right now, just as you see it!

If you have not yet run this module, do so now.
Type the F5 function key, or choose 'Run Module' from the 'Run' menu above.

If you do not want to find any digits of pi, just enter 0.  : )

Type 'factors(12)' at the prompt:

>>> factors(12)

You will get [1, 2, 3, 4, 6, 12] as a response.

Type 'factors(38743)' at the prompt:

>>> factors(38743)

You will get [1, 17, 43, 53, 731, 901, 2279, 38743] as a response.

Certainly these days it would be easy to find a program that would find factors
like this for you.  This has been programmed in many ways by many people.

However, the fact that something has 'already been done' does not at all imply
that it is a waste of time to do it yourself.

Certainly there are times when we don't want to have to 're-invent the wheel',
but in education sometimes that's PRECISELY what we want to do!

The fact that the Pythagorean Theorem has already been proven does not
invalidate your own efforts to think it through yourself.

Thinking through something yourself and coming to understand it is really what
education is about, isn't it?

Here is another problem to consider - how would you define gcf(a, b)?

We know how to explain gcf in words, but how would you define it algebraically?

Again, this is something that various calculators may already be able to give
you, but our goal here is to think it through ourselves.

Consider Euclid's treatment - the gcf of two numbers is either the remainder
itself when the smaller is subtracted from the larger, or it is a factor of
their remainder.

Here is a possible definition:
~ '''
def gcf(a, b):
    if a == b: return a
    if a > b: return gcf(a-b, b)
    if a < b: return gcf(a, b-a)
'''
This definition says

    If a is equal to b, then a or b is the greatest common factor.
    If a is greater than b, then use b to measure a.
    If a is smaller than b, then use a to measure b.
    Find the greatest greatest common factor of the smaller and the remainder.
    That will be the gcf of a and b.

And, of course, this definition works!  Try it out:

>>> gcf(48, 60)
12
>>> gcf(2431, 4420)
221

Here we have a beautiful example of recursion.  Recursion is one of those
'useless' topics in the typical math curriculum, but in the computational
world it is used all the time.

Now, this is not the most efficient form of the algorithm.  Hopefully it is
understandable, but it can be made more efficient by using modulo '%'.
~ '''
def gcf(a, b):
    if b == 0: return a
    return gcf(b, a % b)
'''
Now that we have defined factors(n), we can use it as a component for
constructing models of other concepts.

For example, how would we define 'isprime'?

Well, since a prime number has only two factors, if n is prime, wouldn't it be
the case that the list returned by factors(n) would have a length of only 2?

So we could define isprime this way:
~ '''
def isprime(n): return len(factors(n)) == 2
'''
If you have run this module, then you will be able to have the following
Shell interactions:

>>> isprime(2)
True
>>> isprime(1)
False
>>> isprime(10751)
False
>>> isprime(10909)
True

Now we can use isprime to create lists of primes between a and b:
~ '''
def primes(a, b): return [x for x in range(a, b+1) if isprime(x)]
'''
Our definition means that 'the primes between a and b', inclusive, is a list of
numbers x ranging from a through b where x is prime.

>>> primes(700, 900)
[701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,
 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887]

Notice that we have only required a few lines of code for this!  However, these
lines can interact with each other.  This division of a concept into modular
components is the heart of computational analysis.  This modular organization of
ideas not only makes our programs easier to read and maintain, it can help us
organize our thinking as a whole.

Please notice here, we are not just 'using technology' as a tool to help us
solve problems!  The deeper point is that we are articulating our understanding.
Writing in the curriculum?  Hmmm...

Now let's turn our attention to statistics.

Here's an easy definition for the mean of a list:
~ '''
def mean(L): return sum(L)/len(L)
'''
The 'mean of a list of numbers L' is the sum of L divided by the length of L.

Here's a definition for what we mean by deviation scores:
~ '''
def deviations(L): return [x - mean(L) for x in L]
'''
The 'deviation scores of L' is a list containing the differences between x and
the mean of L for each x in L.

Here's a definition for the squares of a list:
~ '''
def squares(L): return [x**2 for x in L]
'''
The 'squares of L' is a list containing the square of x for each x in L.

Variance is the mean of the squared deviations:
~ '''
def variance(L): return mean(squares(deviations(L)))
'''
The 'variance of a list L' is the mean of the squares of the deviations of L.

Finally, standard deviation is the square root of variance:
~ '''
def stdev(L): return sqrt(variance(L))
'''
These little lines of code are packed with meaning.
What's more, you can read them in their own terms.
They could serve as a student's notes.

These computational descriptions not only can DO the computations themselves,
they can also serve as an explanation of the traditional formulas.

Compare these lines to the formulas written in traditional syntax.
The traditional syntax looks like Greek!  : )

Here is another example - our old friend the quadratic formula.
~ '''
def quadroots(a, b, c):
    h = -b/(2*a)            ## h is the axis of symmetry
    d = b**2 - 4*a*c        ## d is the discriminant
    r = sqrt(abs(d))/(2*a)  ## r is the distance to the roots
    if d < 0: r *= 1j       ## if d is negative, r is imaginary
    return [h - r, h + r]     
'''
Clearly all the components of the traditional quadratic formula are present.

However - we have not blindly 'coded' the quadratic formula.  We have provided
a concept map.  We have analyzed the formula into its essential parts.

Not only that, you guessed it, we can also USE it!

>>> quadroots(2, 17, 8)
[-8.0, -0.5]
>>> quadroots(1, 2, 3)
[(-1-1.4142135623730951j), (-1+1.4142135623730951j)]

Finally, let us define the following:
~ '''
def domain(a, b, dx): return [a+i*dx for i in range(1 + int((b-a)/dx))]
'''
This defines a discrete interval from a to b inclusive.

~ '''
def trapezoid(base1, base2, height): return height*(base1+base2)/2
'''
This defines the area of a trapezoid, obviously.

~ '''
def trapezoids(f, a, b, dx):
    return [trapezoid(f(x), f(x+dx), dx) for x in domain(a, b, dx)]
'''
This defines a list of trapezoids in the interval [a, b] whose bases are f(x)
and f(x+dx) and whose height is dx.

The parameter 'f' can represent any function defined in [a, b].
Functions can be used as parameters in Python.

If you are wondering, 'Well, how would I USE this?':

>>> def f(x): return x**2

>>> for dx in [1, .1, .01, .001, .0001, .00001]: sum(trapezoids(f, 0, 5, dx))

73.0
44.225500000000004
41.917250499999994
41.691672500499898
41.669166725000451
41.666666666750693

>>> def g(x): return 2**x

>>> for dx in [1, .1, .01, .001, .0001, .00001]: sum(trapezoids(g, 0, 5, dx))

94.5
48.056288676088272
45.044838218445221
44.755559152387626
44.726746396371709
44.723546267736225

With a computational language in hand, or mind, we can build the tools we use to
model our understanding.

This is what is happening in the sciences these days.  Scientists cannot rely on
already existing sofware packages to be able to express the ideas they are
working on.  What they need is an easy to use language that is also robust.  For
many, Python fits the bill.

===============================================================================

Following is a version of Gibbon's spigot algorithm.  This is rather cutting
edge stuff.  It was published in American Mathematical Monthly in 2006.

The function pi_gen is a generator.  You'll notice it has 'yield' instead of
'return'.  This means that the function remains 'on call' after returning a
value.  It remembers its state in generating a set of values. Generators are
very useful in constructing sequences.  This a new concept in programming.

~ '''
def pi_gen():
    '''generator for digits of pi'''
    k, a, b, a1, b1 = 2, 4, 1, 12, 4
    while True:
        p, q, k = k*k, 2*k+1, k+1
        a, b, a1, b1 = a1, b1, p*a+q*a1, p*b+q*b1
        d, d1 = a/b, a1/b1
        while d == d1:
            yield(int(d))
            a, a1 = 10*(a%b), 10*(a1%b1)
            d, d1 = a/b, a1/b1
'''
The function pidigits uses pi_gen to create a list of the first n digits of pi.
~ '''
def pidigits(n):
    '''returns a list of n digits of pi'''
    digit = pi_gen()
    return [digit.next() for i in range(n)]
'''
The function freshpi is interactive.  It utilizes functions from the system
module simply to keep things moving.  With just a simple print statement, after
a few thousand digits, things would really start to slow down.
~ '''
import sys
def freshpi():
    n = input('How many digits of pi would you like to generate today? ---> ')
    print
    p = pi_gen()
    for i in range(n):
        sys.stdout.write(str(p.next())+' ')
        sys.stdout.flush()

freshpi()