Dr. Robert Harley on Tue, 6 May 2003 16:31:42 +0200 (CEST)


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Rademacher formula for p(n) with PARI


Hi all,

Bill wrote:
> [...]
> * This program is basically the implementation of the script
. * [...]
> * part(n) = round(sum(q=1,max(5,0.24*sqrt(n)+2),L(n,q)*Psi(n,q)))

Hmm... that formula doesn't take enough terms of Rademacher's series,
when n is small.  In particular it gives p(244) = 144867692496446
instead of 144867692496445 and p(259) = 459545750448674 instead of
459545750448675.  Checking in the source of 2.2.5, what it actually
uses is: max = (ulong)(sqrt(gtodouble(n) ) * 0.24 + 5); which is
enough.

For large n (more than about 250K) the number of terms can be reduced
using Thm 14 from Lehmer's paper (as in the script I posted).  This
can make a noticeable difference since the time to compute the terms
grows quickly.  Perhaps this could be incorporated into Ralf's code to
speed it up for such arguments?  (No, I'm not volunteering to do so! :)

Regards,
  Rob.
     .-.                                                               .-.
    /   \           .-.                                 .-.           /   \
   /     \         /   \       .-.     _     .-.       /   \         /     \
  /       \       /     \     /   \   / \   /   \     /     \       /       \
 /         \     /       \   /     `-'   `-'     \   /       \     /         \
            \   /         `-'                     `-'         \   /
             `-'                                               `-'