20100615, 07:19  #1 
8829_{10} Posts 
(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: http://www.research.att.com/~njas/sequences/A171381 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. 
20100615, 14:20  #2 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17×251 Posts 
If they are PRPs, they aren't on the Top PRP list, where they would place very nicely (at 500298 and 2001192 digits, respectively).
I've completed some preliminary TF (to 100000, using PARI/gp) and P1 ("3^1048576+1 completed P1, B1=10000, B2=185000" and "3^4194304+1 completed P1, 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) Last fiddled with by MiniGeek on 20100615 at 14:21 
20100615, 15:05  #3 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17·251 Posts 
Prime95 finished and reported:
Code:
3^1048576+1/2 is a probable prime! Wd1: A1746598,00000000 Anyone know of a program that can run tests like this faster? Last fiddled with by MiniGeek on 20100615 at 15:21 
20100615, 15:10  #4 
Banned
"Luigi"
Aug 2002
Team Italia
1001011001100_{2} Posts 

20100615, 15:34  #5 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
4267_{10} Posts 
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.
Last fiddled with by MiniGeek on 20100615 at 15:41 
20100615, 15:48  #6  
Jun 2003
11×449 Posts 
Quote:
EDIT: I see that you have already used it. Last fiddled with by axn on 20100615 at 15:49 

20100615, 17:54  #8  
Feb 2005
2^{2}·3^{2}·7 Posts 
Quote:
The main one that refers to the others is http://www1.unihamburg.de/RRZ/W.Keller/GFNfacs.html 

20100615, 18:08  #9 
Feb 2005
2^{2}·3^{2}·7 Posts 
It does have a problem. The reason is similar to why base 2 does not work for Wagstaff numbers  see http://mersenneforum.org/showpost.ph...2&postcount=44 for details.

20100615, 19:51  #10 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}·5^{2}·47 Posts 
Every time I type GFN, I have to doublecheck (and I didn't, above!).
Not only because of dyslexia, but because there's a certain research institute called GNF. 
20100615, 22:22  #11 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17×251 Posts 
Code:
Generic modular reduction using generic reduction FFT length 192K on A 1661953bit number (3^(2^20)+1)/2 is composite: RES64: [AA44F4C19920B7C6] (17978.0246s+0.0577s) 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. Last fiddled with by MiniGeek on 20100615 at 22:24 