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

[Aurel Page <aurel.page@normalesup.org>]

Dear Hermann,

There are two prime testing functions in pari:
- ispseudoprime: a fast pseudo-primality test, which in particular 
guarantees primality of numbers up to 2^64.
- isprime: a certified primality test, which only runs ispseudoprime for 
numbers up to 2^64, but performs a much more costly test otherwise.
In addition, as you know you should expect operations on integers that 
do not fit in a long to be much slower, as we immediately switch to 
multiprecision integers (t_INT).
I did a quick test on my laptop (don't consider these numbers as universal):
- ispseudoprime was about 17 times slower for numbers between 2^63 and 
2^64 than for numbers between 2^64 and 2^65 (long -> t_INT).
- isprime was about 12 times slower than ispseudoprime for numbers 
between 2^64 and 2^65.
Together, these make a jump of x200 for isprime from [2^63,2^64] to 
[2^64,2^65].

Note that 2^64 ~ 10^19, corresponding to your observed jump.

For specific applications, of course a dedicated sieve will be faster 
than individual primality tests.

Cheers,
Aurel

On 06/01/2026 09:30, hermann@stamm-wilbrandt.de wrote:
> I recently submitted https://oeis.org/draft/A392244 on "Number of 
> primes of the form b^2 + (b+1)^2 for b <= 10^n.".
>
> PROG section has this straightforward PARI script:
>
> a(n)=sum(k=1, 10^n, isprime(k^2+(k+1)^2));
>
> It is quite fast for up to n=9 (5 minutes on AMD 7950X CPU). And it 
> computed a(10) as well, but did need 23h for that:
>
> ? a(10)
>
> cpu time = 33h, 53min, 56,970 ms, real time = 23h, 3min, 55,987 ms.
> 614983774
> ?
>
> So is there an isprime() runtime jump between 10^18 and 10^20?
>
>
> There is a conjecture that pi_{k^2+1)(10^n) is a minorant of pi(10^n) 
> = pi_{k}(10^n), with limit factor of 0.686413 (https://oeis.org/A206709).
>
> New sequence conjecture is lim_{k->oo} pi_{k^2+(k+1)^2}/pi_{k^2+1} = 
> 2, so p_{k^2+(k+1)^2} is majorant of prime counting funtions pi(). 
> There are much more primes for k<=10^n in k^2+(k+1)^2 than in natural 
> numbers up to 10^k, which is confirmed by counts up to 10^11.
>
>
> I did create a non-PARI C++ code that traverses a related great 
> grandparent DAG for a "sieve of Eratosthenes like" sieving, which is 
> described here:
>
> https://gist.github.com/Hermann-SW/4b197c6e8bf9f65c7a074ad6271ddce4#file-parallel_dfs_bfs_evenly-cc-L26-L53 
>
>
> Sequential code did compute a(10) in 22min and first parallel version 
> a(11) in 14:28h (on 192C/384T 8-socket server). The directed acyclic 
> graph traversed contains all sum of successive squares composite 
> numbers, allowing to sieve without prime test. Servers's 1TB ram 
> allowed to have 100GB array for sieve. The height of that directed 
> acyclic graph is 40% of 10^n, with is 40 billion(!) for n=11. I never 
> had to traverse such a deep directed acyclic graph ...
>
>
> Regards,
>
> Hermann.