mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Prime Gap Searches

Reply
 
Thread Tools
Old 2021-05-06, 23:10   #34
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

22·7·13 Posts
Default

Quote:
Originally Posted by CraigLo View Post
I took another look at the CRT offsets. I was surprised by how much worse the CRT_6727 did at finding 220k gaps even though it had significantly fewer remaining candidates. We have CRT offsets with 6776, 6751, and 6727 remaining candidates. There is a 4th that was optimized for a merit of 15 that has 6840 remaining candidates. These are all variations on 7993#/13# so I added a fifth to the test, 2347*7993#/13# with 6850 remaining candidates.

The ranking based on probability of finding a gap>220k is OPT_15, 7993#/13#, 6776, 6751, 6727 with 6727 significantly worse than the others. The rankings are almost the inverse of the number of candidates remaining.
I coded up this and a lot more for `gap_stats` where I dynamical calculate the odds that each offset is part of a prime record. It was the next logical step in the optimization for me; technically this makes my code ~20% faster to find record gaps, but the naive code captures ~70% of that benefit so it's a smaller gain and took hundreds of hours of meticulous coding and debugging.

pseudo code is

Code:
For m in range(1, 10^9):
  N = m * P#/K

  prob_record = 0
  for x_i, x in (N + x | no small factors)
    for y_i, y in (N - y | no small factors)
      if record[x+y] > N:
        prob_record += prob_prime ^ 2 + (1- prob_prime) ^ (x_i + y_i)
sadly it's slightly less useful than expected. I found that I was often sieving less than half the distance to the smallest possible records so I had to augment both side with a list of numbers coprime to P#/K


I included a picture from N = m * 1511# / 312270.

"extended^2" looks at records that would be outside on both sides of the sieve.
"extended" refers to records that inside "sieve length" (distance on one side of N sieved) on one but not the other side.

In this example. till you sieve 20K (~13merit) on each side it's hard to judge the probability of a record (min merit ~24) based on just the sieve; you have to look at number of candidates + look outside one or two sides of the sieve.

The second and third graph tell us that the variance (the chance any given m is a record) as sieve length increases up to a 25,000 (16Merit)

I spent ~100 hours trying to understand why the probability decreases in the transition from extended to direct computation. Intuitively the average probability that an interval is a record prime gap is roughly the same before and after we sieve it (some get more likely, some get less likely). I think my code doesn't account for some asymmetry (e.g. if m%3 = 1 then upper and lower gap can't both be % 3 == 2), I'm incorrectly computing something, or ???.
Attached Thumbnails
Click image for larger version

Name:	Screenshot from 2021-05-06 15-49-31.png
Views:	71
Size:	35.4 KB
ID:	24821  
SethTro is offline   Reply With Quote
Old 2021-05-08, 21:29   #35
CraigLo
 
Mar 2021

53 Posts
Default

Attached is a plot showing the probability that a number is included in a gap of 220k for 2347*2993#/13#. The blue plot is the actual curve. The orange curve is the function exp(-(abs(x/220000))^3.3*5.8).

I used the curve fit and calculated a score for each of the offsets. The score is the sum of the probability for each remaining candidate in the interval +/- 220k.

Code:
Offset            Remaining     Score    Prob>220k
CRT_OPT15          6840          7536     7.30E-6
2347*7993#/13#     6850          7545     7.13E-6
CRT_6776           6776          7581     6.92E-6
CRT_6751           6751          7601     6.83E-6
CRT_6727           6727          7704     5.99E-6
The score computed this way properly ranks the candidates based on probability of finding a gap > 220k. I think this approach can be used for finding the best CRT offset, but the function used will change based on the primorials.
Attached Thumbnails
Click image for larger version

Name:	Prob.png
Views:	63
Size:	23.7 KB
ID:	24836  
CraigLo is offline   Reply With Quote
Old 2021-05-09, 08:43   #36
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

61·97 Posts
Default

Are you suggesting that we search m*2347*7993#/13#?
henryzz is offline   Reply With Quote
Old 2021-05-10, 16:15   #37
CraigLo
 
Mar 2021

5310 Posts
Default

Quote:
Originally Posted by henryzz View Post
Are you suggesting that we search m*2347*7993#/13#?
That is the best if you limit the optimization to A*7993#/13#. These were easy for me to check.

The one you called optimized for merit 15 (or 20) is a bit better. We can probably do even better.
CraigLo is offline   Reply With Quote
Old 2021-05-10, 16:49   #38
CraigLo
 
Mar 2021

1101012 Posts
Default

Quote:
Originally Posted by SethTro View Post
I coded up this and a lot more for `gap_stats` where I dynamical calculate the odds that each offset is part of a prime record. It was the next logical step in the optimization for me; technically this makes my code ~20% faster to find record gaps, but the naive code captures ~70% of that benefit so it's a smaller gain and took hundreds of hours of meticulous coding and debugging.
That's interesting. I hadn't considered using this to choose best offsets after sieving. At the moment I am just thinking about finding the best offset (x) so that A*P# + x gives the best chance of finding a large gap.

I'm not sure how much time is spent computing the prob_record but you might be able to speed it up using the approach I described above (post 35). You wouldn't be computing probabilities any more but if you just wanted the best offsets it might be useful.


Quote:
Originally Posted by SethTro View Post
I spent ~100 hours trying to understand why the probability decreases in the transition from extended to direct computation. Intuitively the average probability that an interval is a record prime gap is roughly the same before and after we sieve it (some get more likely, some get less likely). I think my code doesn't account for some asymmetry (e.g. if m%3 = 1 then upper and lower gap can't both be % 3 == 2), I'm incorrectly computing something, or ???.


I noticed an effect similar to what you describe once. Take a simple case where the probability of a number being prime is 1%. The probability of no primes in 200 consecutive numbers is

0.99^200 = 0.1340

Now if we sieve and remove 90% of these there are only 20 possible primes left and the probability of a prime is 10%. The probability of no primes is now

.9^20 = 0.1216

Sieving shouldn't change the probability of no primes. We can rewrite the above as

0.99^200 = (0.99^10)^20

For the probability of the gap to stay the same we would need the probability a number is not prime to be 0.99^10 = .9044.
CraigLo is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primorial offsets robert44444uk Prime Gap Searches 7 2018-11-29 08:40

All times are UTC. The time now is 18:15.


Tue Oct 19 18:15:44 UTC 2021 up 88 days, 12:44, 0 users, load averages: 1.19, 1.24, 1.19

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