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

[hermann@stamm-wilbrandt.de]

On 2024-03-20 23:24, hermann@stamm-wilbrandt.de wrote:
> Missing gist link:
> https://gist.github.com/Hermann-SW/558728c025a1f2d3dace008292bac897
I created modified gist code that does not count, but compute all Proth 
primes until n.

- instead cc++ do listput(c, p)
- instead c+=C do L=concat(L,C)

Called with

r=doit(2^40,1,L2);

and written by:

write("/dev/stderr",Vec(vecsort(r)));

You can use it from here (I submitted to oeis.org, but reviews will take 
time):

https://stamm-wilbrandt.de/en/pari-users/a080076.json.txt

Afterwards I verified that count is correct with gist:

hermann@7950x:~$ n=2^40 gp -q < proth.gp
32
45min, 54,738 ms × 24.010 = 18h, 22min, 21,364 ms
122742
^C

hermann@7950x:~$ gp -q
? P=readvec("a080076.json.txt")[1];
? #P
122742
? P[#P]
1099489607681
? 2^40-P[#P]
22020095
? isProth2(p) = !(p >> (valuation(p-1,2)<<1));
? foreach(P,p,if(!isProth2(p),print(p)))
? ##
  ***   last result: cpu time 29 ms, real time 29 ms.
?


Having all Proth primes up to 2^40 allows to analyze distribution
of Proth primes for all 1<=m<=20 (p=k*2^m+1, k<2^m) for a given m.


Regards,

Hermann.