number theory libraries / project euler

[Kurt Smith]

On Wed, Feb 18, 2009 at 2:18 PM, eliben <eliben at gmail.com> wrote:
>
> Hello,
>
> What are some good & recommended number theory libs for Python (or
> accessible interfaces to C libs), for things like primes,
> factorization, etc. Naturally, speed is of utmost importance here.
>
> In other words, which Python libraries and tools to you use to help
> you solve Project Euler problems :-) ?

There's Sage: http://www.sagemath.org/ -- I believe it aims to do
everything that Mathematica can do and more, and I know it has some
number theory libs, too.  I haven't had the occasion to use it myself.

Much of the fun of project euler problems is 'rolling your own,' or
implementing a classic algorithm from a description of it on
Wikipedia.  A good sieve of eratosthenes in pure Python (that I tend
to use quite often) is here:

http://code.activestate.com/recipes/117119/

You can find some combinatorics in numpy, I believe.

Often the solutions are one-to-five liners, if you've thought the
problem through.  Too much dependence on external libraries robs the
project euler problems of their fun, IMO.

Best,

Kurt