mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2010-06-15, 07:19   #1
Unregistered
 

2·5·172 Posts
Default (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.
  Reply With Quote
Old 2010-06-15, 14:20   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

426710 Posts
Default

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
Mini-Geek is offline   Reply With Quote
Old 2010-06-15, 15:05   #3
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

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
Mini-Geek is offline   Reply With Quote
Old 2010-06-15, 15:10   #4
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

112668 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
Code:
3^1048576+1/2 is a probable prime! Wd1: A1746598,00000000
ET_ is offline   Reply With Quote
Old 2010-06-15, 15:34   #5
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102538 Posts
Default

Quote:
Originally Posted by ET_ View Post
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
Mini-Geek is offline   Reply With Quote
Old 2010-06-15, 15:48   #6
axn
 
axn's Avatar
 
Jun 2003

47×103 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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
axn is offline   Reply With Quote
Old 2010-06-15, 17:21   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

242916 Posts
Default

Max Alexeyev pointed out that W.Keller extended (in 2008) his GNF base-6,10,12 webpages to also GNF03 and GNF05.
Batalov is offline   Reply With Quote
Old 2010-06-15, 17:54   #8
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Quote:
Originally Posted by Batalov View Post
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 is offline   Reply With Quote
Old 2010-06-15, 18:08   #9
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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.
maxal is offline   Reply With Quote
Old 2010-06-15, 19:51   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,257 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2010-06-15, 22:22   #11
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

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
Mini-Geek is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 12:02.

Sat Jan 16 12:02:04 UTC 2021 up 44 days, 8:13, 0 users, load averages: 2.00, 1.91, 1.75

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.