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

2010-06-15, 07:19

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.

Mini-Geek · 2010-06-15, 14:20

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)

Mini-Geek · 2010-06-15, 15:05

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?

ET_ · 2010-06-15, 15:10

Quote:

Originally Posted by Mini-Geek

Code:

3^1048576+1/2 is a probable prime! Wd1: A1746598,00000000

Mini-Geek · 2010-06-15, 15:34

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.

axn · 2010-06-15, 15:48

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.

Batalov · 2010-06-15, 17:21

Max Alexeyev pointed out that W.Keller extended (in 2008) his GNF base-6,10,12 webpages to also GNF03 and GNF05.

maxal · 2010-06-15, 17:54

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

maxal · 2010-06-15, 18:08

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.

Batalov · 2010-06-15, 19:51

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.

Mini-Geek · 2010-06-15, 22:22

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.

2010-06-15, 07:19	#1
Unregistered 3·1,973 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 1000010101011₂ 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, 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

2010-06-15, 17:21	#7
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9,391 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, 19:51	#10
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9,391 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.