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

The OEIS is discussing the primality of (3^(2^20)+1)/2 and (3^(2^22)+1)/2

C.f. the links in:
[url]http://www.research.att.com/~njas/sequences/A171381[/url]
Numbers n such that (3^n + 1)/2 is prime.

Has someone tested these numbers?

How long a pseudoprime test is expected to take on a high end commodity PC?

Thank you.

If they are PRPs, they aren't on [URL="http://www.primenumbers.net/prptop/prptop.php"]the Top PRP list[/URL], where they would place very nicely (at 500298 and 2001192 digits, respectively).
I've completed some preliminary TF (to 100000, using PARI/gp) and P-1 ("3^1048576+1 completed P-1, B1=10000, B2=185000" and "3^4194304+1 completed P-1, B1=20000, B2=175000"). I'll run PRP tests for both of them using Prime95. The smaller one should take about an hour, the larger closer to 15 hours. (each using two cores)

Prime95 finished and reported:
[CODE]3^1048576+1/2 is a probable prime! Wd1: A1746598,00000000[/CODE]
I think it may have a problem checking base 3 GFNs, because it also says [URL="http://factordb.com/search.php?id=45266494"](3^128+1)/2[/URL] is PRP when it's really composite. (come to think of it, I think its PRP base is 3, which means any number like this will return PRP) I'm rerunning (3^(2^20)+1)/2 with PFGW with the PRP base set to 7 (which correctly says (3^128+1)/2 is composite and (3^64+1)/2 is PRP). I'm not going to check (3^(2^22)+1)/2, since that would take a couple of days without being able to use Prime95's multithreading.

Anyone know of a program that can run tests like this faster?

[QUOTE=Mini-Geek;218703][CODE]3^1048576+1/2 is a probable prime! Wd1: A1746598,00000000[/CODE][/QUOTE]

:exclaim::tu:

[QUOTE=ET_;218705]:exclaim::tu:[/QUOTE]

Unfortunately, that test was bad, (whether the result is truly bad is still to be seen, but the test was bad) as my edits to that post indicate. Prime95's PRP uses a base of 3, which makes all numbers of this form return PRP.

[QUOTE=Mini-Geek;218710]Unfortunately, that test was bad, (whether the result is truly bad is still to be seen, but the test was bad) as my edits to that post indicate. Prime95's PRP uses a base of 3, which makes all numbers of this form return PRP.[/QUOTE]

You can use PFGW to force a different base.

EDIT:- I see that you have already used it.

Max Alexeyev pointed out that W.Keller extended (in 2008) his GNF base-6,10,12 webpages to also [URL="http://www1.uni-hamburg.de/RRZ/W.Keller/GFN03.html"]GNF03[/URL] and [URL="http://www1.uni-hamburg.de/RRZ/W.Keller/GFN05.html"]GNF05[/URL].

[QUOTE=Batalov;218726]Max Alexeyev pointed out that W.Keller extended (in 2008) his GNF base-6,10,12 webpages to also [URL="http://www1.uni-hamburg.de/RRZ/W.Keller/GFN03.html"]GNF03[/URL] and [URL="http://www1.uni-hamburg.de/RRZ/W.Keller/GFN05.html"]GNF05[/URL].[/QUOTE]

Actually, there are even more pages on factors of GNF's in different bases.
The main one that refers to the others is
[url]http://www1.uni-hamburg.de/RRZ/W.Keller/GFNfacs.html[/url]

[QUOTE=Mini-Geek;218703]I think it may have a problem checking base 3 GFNs[/QUOTE]
It does have a problem. The reason is similar to why base 2 does not work for Wagstaff numbers - see [url]http://mersenneforum.org/showpost.php?p=207182&postcount=44[/url] for details.

:doh!: Every time I type GFN, I have to double-check (and I didn't, above!).

Not only because of dyslexia, but because there's a certain research institute called GNF.

[CODE]Generic modular reduction using generic reduction FFT length 192K on A 1661953-bit number
(3^(2^20)+1)/2 is composite: RES64: [AA44F4C19920B7C6] (17978.0246s+0.0577s)[/CODE]
As mentioned before, this was with a PRP base of 7.

Since that base 3 GFN page says that this number was previously unknown, I'll email this result to Wilfrid Keller.
And yes, it took almost exactly 5 hours on one full core, even though Prime95 with 2 cores only took about 1 hour. Apparently PFGW is much slower than Prime95 for this sort of thing.