20111011, 04:32  #1 
Aug 2006
3·19·103 Posts 
CRUSlike sieving challenge
The challenge: extend A181356. This will require sieving a large range and then checking for probable primes.
I'm curious as to why the existing numbers are so large. (Or maybe it's just late at night and they are the expected size but I don't realize it.) Last fiddled with by CRGreathouse on 20111011 at 04:32 
20111011, 06:39  #2 
Romulan Interpreter
Jun 2011
Thailand
5·11·157 Posts 
They are not quite large. 2^2^nk is "tremendous". Primes get scarce at that size, especially when you looking for safe or sophie germain primes (that is, you have to find not only one, but two primes of that size).
One liner in pari, no optimization (school grade method): Code:
for(n=1,20,a=2^(2^n); forstep(k=1,a,2,if(ispseudoprime(b=ak) && ispseudoprime(c=((b1)/2)), print(n", "k); write("A181356.txt",n", "k", "a", "b", "c); break))) 2, 5 3, 29 4, 269 5, 209 6, 1469 7, 15449 8, 36113 9, 38117 I was initially printing all on screen, but the screen got messy so I used the external file. The contents of the output file: Code:
2, 5, 16, 11, 5 3, 29, 256, 227, 113 4, 269, 65536, 65267, 32633 5, 209, 4294967296, 4294967087, 2147483543 6, 1469, 18446744073709551616, 18446744073709550147, 9223372036854775073 7, 15449, 340282366920938463463374607431768211456, 340282366920938463463374607431768196007, 170141183460469231731687303715884098003 8, 36113, 115792089237316195423570985008687907853269984665640564039457584007913129639936, 115792089237316195423570985008687907853269984665640564039457584007913129603823, 57896044618658097711785492504343953926634992332820282019728792003956564801911 9, 38117, 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096, 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006045979, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503022989 Last fiddled with by LaurV on 20111011 at 06:45 Reason: removed the quoted message 
20111011, 11:57  #3  
(loop (#_fork))
Feb 2006
Cambridge, England
6353_{10} Posts 
Quote:
Implying you'd need to check somewhere around a billion numbers of size 2^32768 to find the next one, which is really quite a lot of work (probably six CPUmonths assuming you get 99.9% removal by sieving, which is realistic for safeprimes) Last fiddled with by fivemack on 20111011 at 12:03 

20111011, 12:05  #4 
Aug 2006
3·19·103 Posts 

20111026, 18:41  #5 
May 2007
Kansas; USA
27C0_{16} Posts 
I believe the answer is k=718982153.
2^32768718982153 is PRP 2^32767359491077 is PRP Attempted primality test using the tc option in PFGW: Code:
n=32768: [Oddly several different recent versions of PFGW errored out when attempting the tc option on the n=32768 exponent.] Details: Primality testing 2^32768718982153 [N1/N+1, BrillhartLehmerSelfridge] Running N1 test using base 5 Error 1002 initializing FFT code n=32767: Primality testing 2^32767359491077 [N1/N+1, BrillhartLehmerSelfridge] Running N1 test using base 2 Running N+1 test using discriminant 7, base 2+sqrt(7) Calling N+1 BLS with factored part 0.07% and helper 0.04% (0.25% proof) 2^32767359491077 is Fermat and Lucas PRP! (61.1761s+0.0023s) This took ~46 CPU weeks using unmodified versions of srsieve for sieving and PFGW for PRP testing. All k<1.2G was tested. I sieved n=32768, converted the file, then sieved n=32767, both nvalues to an approximate optimal depth of P=50M. There were ~798,000 tests to run after sieving both sides with an estimated ~1/720 chance of each test being PRP for either side. There were 1138 PRPs on the n=32768 side with also a ~1/720 chance of those being also PRP for n=32767...and one was found. The effective chance of a safe prime (or SophieGermain prime) for this range was ~7580% so I very easily could have found nothing or even 2 or more safe primes. Entries for the PRPs in the factoring DB are at: http://factorization.ath.cx/index.ph...2768718982153 http://factorization.ath.cx/index.ph...2767359491077 Does the OEIS site need primality proof? The chance of either one of the PRPs being composite is very tiny. I don't care to run Primo tests on both a 9864 and a 9865digit PRP. The CPU time needed would be more than finding the two PRPs. If they need proof, I'd be glad to share credit with anyone who would run the tests. BTW, this sieving was nothing like the sieving that we do at CRUS, although the title of the thread is what caught my attention. Now...does anyone care to try for the next term at n=65535/65536? Gary 
20111026, 19:24  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×7×11×59 Posts 
For the next one, PRPtop gives us a headstart ...not.
http://www.primenumbers.net/prptop/s...rm=2%5E65536x  these are known PRPs and their counteparts are not PRPs 
20111026, 20:03  #7  
May 2007
Kansas; USA
10011111000000_{2} Posts 
Quote:
2^655352814 has factors: 2 2^6553549634 has factors: 2 2^6553561782 has factors: 2 2^6553586009 has factors: 3 2^65535134142 has factors: 2 2^65535212768 has factors: 2^5 2^65535241025 has factors: 3 2^65535254177 has factors: 3^2 As implied by the title, the main challenge of this effort is sieving both sides to a reasonable limit. It's easy enough to find many PRPs on one side. The challenge is combining the two sides. 

20111026, 20:39  #8  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
http://en.wikipedia.org/wiki/Safe_prime Quote:
Quote:
now if only I could find something else to speed it up. 

20111026, 20:42  #9  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
Quote:


20111026, 20:49  #10 
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 

20111026, 21:00  #11 
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sieving for CRUS  rebirther  Conjectures 'R Us  580  20200312 22:49 
Sieving Drive all base 2/4 k's worked by CRUS  gd_barnes  Conjectures 'R Us  143  20141021 23:55 
Some CRUS stats  vmod  Conjectures 'R Us  213  20140228 21:23 
What are your CRUS plans?  rogue  Conjectures 'R Us  35  20131109 09:03 
how high will CRUS go  MiniGeek  Conjectures 'R Us  1  20101108 20:50 