Re: isprime() runtime jump between 10^18 and 10^20?

On Sat, Jan 10, 2026 at 04:20:18PM +0100, [email protected] wrote:
> On 2026-01-06 20:59, [email protected] wrote:
> > ...
> > Runtime reduced from 5min to 5 seconds, and from 23h to 19 minutes
> > using parsum()!
> > 
> > hermann@x3950-X6:~$ nproc
> > 384
> > hermann@x3950-X6:~$ numactl -C 0-191 gp -q
> > ? a(n)=parsum(k=1, 10^n, isprime(k^2+(k+1)^2));
> > ? #
> >    timer = 1 (on)
> > ? a(9)
> > cpu time = 14min, 51,150 ms, real time = 4,819 ms.
> > 68588950
> > ? a(10)
> > cpu time = 59h, 57min, 42,370 ms, real time = 18min, 46,398 ms.
> > 614983774

In this kind of computation, only the k such that k^2+(k+1)^2 is pseudoprime
actually matter and their density is about 1/log(k^2+(k+1)^2) ~ 1/(2*log(2*k))
which is decreasing, so the number of primes to check is increasing
sublinearly.

Cheers,
Bill.