CRUS-like sieving challenge

[science_man_88]

Originally Posted by 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...

using a version of this with a step of 12 and start of 5 I get to try line 10 in under 17 seconds.

[gd_barnes]

SM88, please stop responding to yourself. It's annoying. Take your time, figure everything out ahead of time, and then make one post.

I don't know if this will help you any but for the n=32768/32767 challenge, for both sides to be prime, for n=32768, the condition k==(17, 29, or 53 mod 60) had to be true. What that condition did was eliminate all factors of 2, 3, and 5 from both n=32767 and 32768. That was the starting point that I used for sieving n=32768. For sieving n=65536, although the modulos will be different, the idea will be the same.

[science_man_88]

Originally Posted by gd_barnes

SM88, please stop responding to yourself. It's annoying. Take your time, figure everything out ahead of time, and then make one post.

I don't know if this will help you any but for the n=32768/32767 challenge, for both sides to be prime, for n=32768, the condition k==(17, 29, or 53 mod 60) had to be true. What that condition did was eliminate all factors of 2, 3, and 5 from both n=32767 and 32768. That was the starting point that I used for sieving n=32768. For sieving n=65536, although the modulos will be different, the idea will be the same.

okay,sorry, it's probably just that I never catch everything so I'd never post under those conditions.

[Batalov]

Originally Posted by gd_barnes

...for n=32768, the condition k==(17, 29, or 53 mod 60) had to be true...

For sieving n=65536, the condition is the same.

[Batalov]

For an estimate how large the k₁₆ might be, here's the first PRP from 65536 side after the 2-side sieve (but not the other): 2^65536-2723249.

So, that's one PRP down, with a few thousand more to find and test on the other side until both are PRPs.

P.S. oh, here came another: 2^65536-2912969...

[gd_barnes]

Originally Posted by Batalov

For an estimate how large the k₁₆ might be, here's the first PRP from 65536 side after the 2-side sieve (but not the other): 2^65536-2723249.

So, that's one PRP down, with a few thousand more to find and test on the other side until both are PRPs.

P.S. oh, here came another: 2^65536-2912969...

Using my time of 4-6 CPU weeks for the n=32768 testing, it would take 16 times as long to do the n=65536 testing, as follows:

1. The tests take 4 times as long.
2. Half as much chance of n=65536 (vs. n=32768) being prime so twice as many tests.
3. Half as much chance of n=65535 (vs. n=32767) being prime so twice as many tests.

4x2x2=16 times as long and 4 times the k-range.

So you can assume that it would take 64-96 CPU weeks or 1-2 CPU years with current sieving/testing technology to find an n=65536 safe prime using srsieve/PFGW like I did.

To have a 75-80% chance of safe prime at n=65536, you would want to sieve all k<~5G.

The key is for someone to come up with a better sieving program. P=50M was the approximate and very low optimum sieving limit for n=32768 because srsieve has to handle each k as a separate sequence for a single n and so is very slow. As a general rule, it can only effectively sieve ~100,000 sequences reasonably efficiently. Beyond that and it loses a lot of efficiency.

Personally I had to start out sieving in k=2M groups starting with all k==(17, 29 or 53 mod 60). 3 out of every 60 k's meant 100,000 k's in each k=2M group. I had to do that 600 times for the entire k<=1.2G range, i.e. 2M*600=1.2G. Once I had the # of sequences reduced after sieving the first go around, I could then sieve the other side in 120 k=10M groups. (Actually there were more sieving steps than that to increase CPU sieving efficiency but they are a moot point for this explanation. Also, this is definitely the limit of manual effort that anyone would want to do for such an excercise. It is very impractical for n=65536; requiring 4 times the # of sieving groups.)


Gary

[gd_barnes]

Originally Posted by gd_barnes

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.

Can anyone give me an answer to the above? If PRPs are good enough for them, I'll go ahead and submit them to the OEIS site.

[Batalov]

Usually, yes (unlike UTM Primes). With a clear note that they are PRP.

[gd_barnes]

Originally Posted by Batalov

Usually, yes (unlike UTM Primes). With a clear note that they are PRP.

I have submitted the proposed change. This is my first submission to OEIS. We'll see if it is accepted.

That was kind of fun.

[wblipp]

Originally Posted by gd_barnes

I don't care to run Primo tests on both a 9864 and a 9865-digit PRP.

You only need Primo on the smaller one. You can then use it in an N-1 proof for the larger one.

[Batalov]

Originally Posted by gd_barnes

The key is for someone to come up with a better sieving program. P=50M was the approximate and very low optimum sieving limit for n=32768 because srsieve has to handle each k as a separate sequence for a single n and so is very slow. As a general rule, it can only effectively sieve ~100,000 sequences reasonably efficiently. Beyond that and it loses a lot of efficiency...

Well, 2^(2^n)-k sieve in k should be an appallingly easy sieve to write from scratch and even without GMP (raising 2^(2^n) mod p is very easy and then just zero some bits), but will it do better than a "sieve" like this?

# gp -p 80000000
write("kcan","ABC 2^65536-$a")
forstep(k=17,99999999,12, \
   if(k%60==17||k%60==29||k%60==53, \
   m=1;forprime(p=7,80000000,if(lift(Mod(2,p)^65536-k)<2,m=0;break)); \
   if(m>0,write("kcan",k))) \
)

and after a bit of time start "pfgw -f0 -llog kcan" in parallel?