(3^(2^20)+1)/2 and (3^(2^22)+1)/2

[Batalov]

Prime95 does a better version of the test. It is described somewhere on the forum. It sets the denominator aside. I believe that this is the same trick as implemented in Magma examples in one of these OEIS sequences:
IsPrime((3^(2^15)+1) div 2); <-- not the div, not "/"

In PFGW, forms with denominator turn a test number into a general number, therefore computation gets much slower even though the GW library is the same.

OTOH, in Prime95, base 3 is solidly entrenched into the source (see file commonb.c, function prp (); I looked at the 2.5.7 source; maybe it had been changed?). Recompilation of Prime95 from source is not easy. We should ask George to make base "b" a parameter of the PRP workunit, eh?

[fivemack]

How painful is it to use a base like 3^10 rather than 2^16 for FFT arithmetic? Sounds like two double-length multiplies per digit in the carry-propagation, and in return the modulus operations become trivial, which looks like not a bad tradeoff.

Or is PFGW already doing something cleverer and DWT-like for these ultra-round base-N numbers?

[Jens K Andersen]

Originally Posted by Batalov

In PFGW, forms with denominator turn a test number into a general number, therefore computation gets much slower even though the GW library is the same.

Some PFGW versions can make fast prp tests of cofactors of optimized forms if the cofactor is written in a way recognized by PFGW. Compare these:

C:\pfgw-work>pfgw -N -b7 base3.txt
PFGW Version 3.3.3.20100325.Win_Stable [GWNUM 25.14]

(3^(2^16)+1)/2 is composite: RES64: [CDBC220B876B71AC] (98.7510s+0.0023s)
(3^65536+1)/2 is composite: RES64: [CDBC220B876B71AC] (18.7601s+0.0030s)

[Batalov]

In the older version, there was an interesting feature and when I ran a few-month-long-single-cpu GFN(10,23) test, I used it. I don't remember the details but W.Keller later confirmed that residues matched for it and for the similar GFN(12,22) with Geoff Reynolds' (and unknown to each other and to W.K. we happenned to ran the same tests - well, Geoff was first; he used LLR, though).

It was much faster to run
pfgw -f0 -q"10000^2097152+1"
than
pfgw -f0 -q"10^8388608+1"
(but this was true only in 2008.)

And indeed, as I was crawling the code in 2008 before doing that thing, I found that the parser back then used special GFN DFT only when it recognized a literal request b^N+1 (with upper limits on b and N, so "10^8388608+1" a.f.a.i.r. didn't pass the special GFN DFT recognition pattern). So (3^(2^16)+1)/2, as well as 10^(2^23)+1 would probably not be parsed as GFN, and would go as "general" numbers.

This all (or most of it) has changed in >= 3.3. I can't say that I know the current state of the PFGW code. I know that it is very much better.
__________

Another snippet: I recently ran a family of (k*10^n+1)/9 numbers (they are quasi-repunits of the A888...8889 kind, with k=9*A+8) for PRP, preceeded by srsieve (forget about denominator of 9, run with -p 5; take care of 3 manually). And I can say that Prime95 ran much faster than PFGW for the 3-PRP tests with the "9" as a known factor. I think there's a certain similarity to the (3^N+1)/2 story here.

[Jens K Andersen]

Ah yes, the difference in my example was apparently GFN recognition. Omitting division by 2 gives similar time difference:

C:\pfgw-work>pfgw -N -b7 base3b.txt
PFGW Version 3.3.3.20100325.Win_Stable [GWNUM 25.14]

3^(2^16)+1 is composite: RES64: [B787AA3A66CF6FF7] (97.3374s+0.0023s)
3^65536+1 is composite: RES64: [B787AA3A66CF6FF7] (19.5387s+0.0028s)

[Mini-Geek]

Originally Posted by Jens K Andersen

Some PFGW versions can make fast prp tests of cofactors of optimized forms if the cofactor is written in a way recognized by PFGW. Compare these:

C:\pfgw-work>pfgw -N -b7 base3.txt
PFGW Version 3.3.3.20100325.Win_Stable [GWNUM 25.14]

(3^(2^16)+1)/2 is composite: RES64: [CDBC220B876B71AC] (98.7510s+0.0023s)
(3^65536+1)/2 is composite: RES64: [CDBC220B876B71AC] (18.7601s+0.0030s)

That's probably why it took me 5 hours instead of closer to 2 hours.

[XYYXF]

http://listserv.nodak.edu/cgi-bin/wa...hry&T=0&P=1143

[Mini-Geek]

Now that I know about this speedup, I'd like to run (3^(2^22)+1)/2 too if nobody else is running or has run it. If you've run it or are in the process of running it, please post here.

I am running it but probably I will not finish it (PFGW crashes when it saves the intermediate results and I may need to reboot.).

Some stats:

I finished 2^20 on a single core in about an hour. Intel 2.6G, 6M L2 .

2^22 so far:
PFGW Version 3.3.4.20100405.x86_Stable [GWNUM 25.14]
5 hours, PRP: (3^4194304+1)/2 2025000/6647813

Base 5.

--j

[Mini-Geek]

Originally Posted by Unregistered

I am running it but probably I will not finish it (PFGW crashes when it saves the intermediate results and I may need to reboot.).

Hm, weird. If you want some help with that problem, try posting in a PFGW thread with more details.

With this in mind, and what Batalov responded to a PM I sent him, (he's not running n=22) I'm running n=22 now (I started a little while ago). I expect it to finish in around 15 hours total, (about 14 hours from now) so if all goes well I'll report the result in the morning (roughly 18 hours from now).

[Batalov]

I'll probably run n=23 in base 2 or 5 and will try to build a modified Prime95 in parallel.

ETA 2.7cpu-days. Surely it is already been done by someone. Anyway.