CRUS-like sieving challenge

[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.)

[LaurV]

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):

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:

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...

[fivemack]

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)

[CRGreathouse]

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.

[gd_barnes]

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:

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

[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

[gd_barnes]

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.

[science_man_88]

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

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

(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 that will help me personally.

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

[science_man_88]

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 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:

(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]

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.

[science_man_88]

Originally Posted by science_man_88

nevermind found my flaw forgot to check if the first part was prime.

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.