number theory libraries / project euler

[eliben]

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 ?

Eli

 

[Kurt Smith]

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

 

[Paul Rubin]

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.

The idea of Project Euler is you are supposed to find clever enough
methods to solve the problems that speed of the software libs is NOT
important.

 

[Mensanator]

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 ?

Eli

Also check out the gmpy library, lots of good number theory stuff
like factorial, gcd, lcm, linear congruence, is_prime, next_prime,
(I even found a use for the legendre function), etc.

(no factorization, I have Python call the MIRACL factor program when
I need that)

gmpy is so vital to my work that if they ever stop supporting it,
I will abandon Python.