Re: How to efficiently count Proth primes with GP parfor?

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* hermann@stamm-wilbrandt.de [2024-03-20 01:53]:
[...]
> ? isProth(p)=v=valuation(p-1,2);p>>v<2^v;
[...]
> ? c=0;forprime(p=3,4636016641,c+=1);c
> 218629816
> ? ##
>   ***   last result: cpu time 28,710 ms, real time 28,711 ms.
> ? c=0;forprime(p=3,4636016641,c+=isProth(p));c
> 10000
> ? ##
>   ***   last result: cpu time 1min, 25,406 ms, real time 1min, 25,408 ms.
> ? c=0;forprime(p=3,4636016641,if(isProth(p),c+=1));c
> 10000
> ? ##
>   ***   last result: cpu time 1min, 9,411 ms, real time 1min, 9,416 ms.
> ?
> 
> So the last two do count Proth primes correctly.
> Can it be done faster sequentially?

Sure. Less readable, though:

  isProth2(p) = !(p >> (valuation(p-1,2)<<1))

On my (slow) laptop:

  (12:55) gp > c=0;forprime(p=3,4636016641,c++);c
  time = 36,980 ms.
  %1 = 218629816

Your version:
  (12:56) gp > c=0;forprime(p=3,4636016641,if(isProth(p),c++));c
  time = 1min, 15,760 ms.
  %2 = 10000

Mine:
  (12:57) gp > c=0;forprime(p=3,4636016641,if(isProth2(p),c++));c
  time = 48,292 ms.
  %3 = 10000

Cheers,

    K.B.
-- 
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/