partition function code available

Ralf Stephan ralf@ark.in-berlin.de
Wed, 11 Dec 2002 16:58:31 +0100


Hello,

the unrestricted partition function p(n) counts the nonnegative integer
solutions to a+2b+3c+...=n. Example: 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 =
2+1+1+1 = 1+1+1+1+1 (7 solutions), so p(5)=7. Read more about it at:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000041

There is code for mpz_t p (unsigned long n) available at
http://www.ark.in-berlin.de/part.c

The function can be computed analytically with the Hardy-Ramanujan-Rademacher 
formula which involves also high precision computation of exp, cos and
Dedekind sums. A one-page summary of formulas used, without refs, is at:
http://www.ark.in-berlin.de/part.pdf

>From anecdotal evidence, speed is comparable to Mathematica. The
implementation uses mpfr, mpq, and mpz, and thus is not easily included in
current GNU MP versions (only if --enable-mpfr is set?).

Question to maintainer(s):
I would submit a patch if you decide where you want it to go (mpz? mpfr?
examples?). In case you don't see a possibility for including, maybe a link
from or a copy at the GMP site would be helpful for others.

Thanks for your consideration,
ralf