mersenneforum.org CRUS-like sieving challenge
 Register FAQ Search Today's Posts Mark Forums Read

 2011-10-11, 04:32 #1 CRGreathouse     Aug 2006 3·1,993 Posts CRUS-like 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 2011-10-11 at 04:32
 2011-10-11, 06:39 #2 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 100110010011102 Posts They are not quite large. 2^2^n-k 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=a-k) && ispseudoprime(c=((b-1)/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 Remark that if I use "isprime()" then at n=8 the waiting time is already over 15 minutes. With "ispseudoprime()" the "bottleneck" is 10 (20 minutes passed, no output yet). For 9 it takes about 1 minute. 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 So, these numbers are tremendous... Last fiddled with by LaurV on 2011-10-11 at 06:45 Reason: removed the quoted message
2011-10-11, 11:57   #3
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

22·32·179 Posts

Quote:
 Originally Posted by CRGreathouse 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.)
They're safe-primes, which are roughly probability 1/(log N)^2; so you'd expect the Nth entry to be of order 4^N, and it is.

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 CPU-months assuming you get 99.9% removal by sieving, which is realistic for safeprimes)

Last fiddled with by fivemack on 2011-10-11 at 12:03

2011-10-11, 12:05   #4
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by fivemack They're safe-primes, which are roughly probability 1/(log N)^2; so you'd expect the Nth entry to be of order 4^N, and it is.
...and that's why I should leave math for the pre-midnight hours.

 2011-10-26, 18:41 #5 gd_barnes     May 2007 Kansas; USA 293316 Posts I believe the answer is k=718982153. 2^32768-718982153 is PRP 2^32767-359491077 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^32768-718982153 [N-1/N+1, Brillhart-Lehmer-Selfridge] Running N-1 test using base 5 Error 1002 initializing FFT code n=32767: Primality testing 2^32767-359491077 [N-1/N+1, Brillhart-Lehmer-Selfridge] Running N-1 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^32767-359491077 is Fermat and Lucas PRP! (61.1761s+0.0023s) Some details: This took ~4-6 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 n-values 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 Sophie-Germain prime) for this range was ~75-80% 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...2768-718982153 http://factorization.ath.cx/index.ph...2767-359491077 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 9865-digit 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
 2011-10-26, 19:24 #6 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23×1,201 Posts For the next one, PRPtop gives us a headstart ...not. http://www.primenumbers.net/prptop/s...rm=2%5E65536-x - these are known PRPs and their counteparts are not PRPs
2011-10-26, 20:03   #7
gd_barnes

May 2007
Kansas; USA

53·199 Posts

Quote:
 Originally Posted by Batalov For the next one, PRPtop gives us a headstart ...not. http://www.primenumbers.net/prptop/s...rm=2%5E65536-x - these are known PRPs and their counteparts are not PRPs
Yeah, unfortunately their counterparts all have factors of 2 or 3 so they don't help us any, i.e.:
2^65535-2814 has factors: 2
2^65535-49634 has factors: 2
2^65535-61782 has factors: 2
2^65535-86009 has factors: 3
2^65535-134142 has factors: 2
2^65535-212768 has factors: 2^5
2^65535-241025 has factors: 3
2^65535-254177 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.

2011-10-26, 20:39   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by CRGreathouse 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.)
I'm trying to figure it out a bit ( reading a bit):

http://en.wikipedia.org/wiki/Safe_prime

Quote:
 Combining both forms using lcm(6,4) we determine that a safe prime q > 7 also must be of the form 12k−1 or, equivalently, q ≡ 11 (mod 12).
PARI

Quote:
 (17:33)>for(n=2,20,print((2^(2^n))%12)) 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
so 4-(-1) = 5 so $k \equiv 5 \text { mod } 12$ that will help me personally.

now if only I could find something else to speed it up.

2011-10-26, 20:42   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by science_man_88 I'm trying to figure it out a bit ( reading a bit): http://en.wikipedia.org/wiki/Safe_prime PARI so 4-(-1) = 5 so $k \equiv 5 \text { mod } 12$ that will help me personally. now if only I could find something else to speed it up.
and with that info I find different values:

Quote:
 (17:34)>for(n=2,15,forstep(k=5,2^(2^n-1)-1,12,if(isprime(((2^(2^n)-k)-1)/2),print(k);break()))) 5 29 101 137 329 77 1469 677

2011-10-26, 20:49   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by science_man_88 and with that info I find different values:
nevermind found my flaw forgot to check if the first part was prime.

2011-10-26, 21:00   #11
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

Quote:
 Originally Posted by science_man_88 nevermind found my flaw forgot to check if the first part was prime.
Quote:
 for(n=2,15,forstep(k=5,2^(2^n-1)-1,12,if(isprime(2^(2^n)-k) && isprime(((2^(2^n)-k)-1)/2),print(k);break())))
I'm guessing using stuff from the other pari code given might help.

 Similar Threads Thread Thread Starter Forum Replies Last Post rebirther Conjectures 'R Us 657 2021-09-01 18:01 gd_barnes Conjectures 'R Us 143 2014-10-21 23:55 vmod Conjectures 'R Us 213 2014-02-28 21:23 rogue Conjectures 'R Us 35 2013-11-09 09:03 Mini-Geek Conjectures 'R Us 1 2010-11-08 20:50

All times are UTC. The time now is 23:45.

Fri Nov 26 23:45:14 UTC 2021 up 126 days, 18:14, 0 users, load averages: 1.36, 1.30, 1.28