mersenneforum.org (3^(2^20)+1)/2 and (3^(2^22)+1)/2
 Register FAQ Search Today's Posts Mark Forums Read

 2010-06-15, 07:19 #1 Unregistered   882910 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.
 2010-06-15, 14:20 #2 Mini-Geek 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 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) Last fiddled with by Mini-Geek on 2010-06-15 at 14:21
 2010-06-15, 15:05 #3 Mini-Geek 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 I think it may have a problem checking base 3 GFNs, because it also says (3^128+1)/2 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? Last fiddled with by Mini-Geek on 2010-06-15 at 15:21
2010-06-15, 15:10   #4
ET_
Banned

"Luigi"
Aug 2002
Team Italia

10010110011002 Posts

Quote:
 Originally Posted by Mini-Geek Code: 3^1048576+1/2 is a probable prime! Wd1: A1746598,00000000

2010-06-15, 15:34   #5
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

426710 Posts

Quote:
 Originally Posted by ET_
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 Mini-Geek on 2010-06-15 at 15:41

2010-06-15, 15:48   #6
axn

Jun 2003

11×449 Posts

Quote:
 Originally Posted by Mini-Geek 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.
You can use PFGW to force a different base.

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

Last fiddled with by axn on 2010-06-15 at 15:49

 2010-06-15, 17:21 #7 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 222708 Posts Max Alexeyev pointed out that W.Keller extended (in 2008) his GNF base-6,10,12 webpages to also GNF03 and GNF05.
2010-06-15, 17:54   #8
maxal

Feb 2005

22·32·7 Posts

Quote:
 Originally Posted by Batalov Max Alexeyev pointed out that W.Keller extended (in 2008) his GNF base-6,10,12 webpages to also GNF03 and GNF05.
Actually, there are even more pages on factors of GNF's in different bases.
The main one that refers to the others is
http://www1.uni-hamburg.de/RRZ/W.Keller/GFNfacs.html

2010-06-15, 18:08   #9
maxal

Feb 2005

22·32·7 Posts

Quote:
 Originally Posted by Mini-Geek I think it may have a problem checking base 3 GFNs
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.

 2010-06-15, 19:51 #10 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23·52·47 Posts 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.
 2010-06-15, 22:22 #11 Mini-Geek 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 1661953-bit number (3^(2^20)+1)/2 is composite: RES64: [AA44F4C19920B7C6] (17978.0246s+0.0577s) 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. Last fiddled with by Mini-Geek on 2010-06-15 at 22:24