mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2011-10-11, 04:32   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

172D16 Posts
Default 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
CRGreathouse is offline   Reply With Quote
Old 2011-10-11, 06:39   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·7·317 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2011-10-11, 11:57   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11000101100102 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
fivemack is offline   Reply With Quote
Old 2011-10-11, 12:05   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111001011012 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2011-10-26, 18:41   #5
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

3×7×487 Posts
Default

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
gd_barnes is online now   Reply With Quote
Old 2011-10-26, 19:24   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

912810 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2011-10-26, 20:03   #7
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

3·7·487 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
gd_barnes is online now   Reply With Quote
Old 2011-10-26, 20:39   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

202618 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-10-26, 20:42   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000101100012 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
science_man_88 is offline   Reply With Quote
Old 2011-10-26, 20:49   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
and with that info I find different values:
nevermind found my flaw forgot to check if the first part was prime.
science_man_88 is offline   Reply With Quote
Old 2011-10-26, 21:00   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sieving for CRUS rebirther Conjectures 'R Us 596 2020-10-04 19:49
Sieving Drive all base 2/4 k's worked by CRUS gd_barnes Conjectures 'R Us 143 2014-10-21 23:55
Some CRUS stats vmod Conjectures 'R Us 213 2014-02-28 21:23
What are your CRUS plans? rogue Conjectures 'R Us 35 2013-11-09 09:03
how high will CRUS go Mini-Geek Conjectures 'R Us 1 2010-11-08 20:50

All times are UTC. The time now is 20:17.

Fri Oct 30 20:17:34 UTC 2020 up 50 days, 17:28, 1 user, load averages: 2.81, 2.24, 2.08

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.