CRT offsets

[CraigLo]

Originally Posted by henryzz

I think this shows that it is necessary to pay attention to the target gap size with these searches.

Yes, but CRT_6727 is only 5th best of the 7 options at 220k and 15% worse than CRT_6776 even though it has the fewest remaining candidates so it is more complicated than just finding the minimum remaining candidates. I still think you would get better results for 220k if you ran the CRT code for a value greater than 220k. You could also try assigning a higher score to candidates near the center and a lower score to candidates farther from the center.

[henryzz]

Originally Posted by CraigLo

Yes, but CRT_6727 is only 5th best of the 7 options at 220k and 15% worse than CRT_6776 even though it has the fewest remaining candidates so it is more complicated than just finding the minimum remaining candidates. I still think you would get better results for 220k if you ran the CRT code for a value greater than 220k. You could also try assigning a higher score to candidates near the center and a lower score to candidates farther from the center.

220k is nearly a record gap at this size(it was until recently). I would expect a lot of records in 120k-160k range. This size range would be better for maximising record gaps/day rather than the overall record.

[CraigLo]

Originally Posted by henryzz

220k is nearly a record gap at this size(it was until recently). I would expect a lot of records in 120k-160k range. This size range would be better for maximising record gaps/day rather than the overall record.

This was a general comment that applies to gaps of any length. I only picked 220k because that was what you used. Finding offsets with fewer remaining candidates over some range does not necessarily lead to better odds of finding a gap of that size.

[henryzz]

Originally Posted by CraigLo

This was a general comment that applies to gaps of any length. I only picked 220k because that was what you used. Finding offsets with fewer remaining candidates over some range does not necessarily lead to better odds of finding a gap of that size.

As far as I understand it optimising a range of x should provide better odds of finding a gap of size y with y < x. We just need to work out the correct ratio of x and y.

[CraigLo]

Originally Posted by henryzz

As far as I understand it optimising a range of x should provide better odds of finding a gap of size y with y < x. We just need to work out the correct ratio of x and y.

I think that is correct. For a target gap size of G, all gaps >= G are going to contain some candidates < -G/2 or > G/2. You can't optimize the result while ignoring all of these.

Probably the best way to calculate this would be to scale the remaining candidates by the probability that they contribute to a gap of size G. Candidates near 0 would have a probability near 1. Candidates near +/- G/2 would have a probability near 0.5. Candidates near +/- G would have a probablility near 0. So run from -G to G and sum the probabilities for all remaining candidates and then minimize this.

I'm guessing you could get similar performance by doing what you suggested. Minimize the remaining candidates for some range > G which needs to be determined.

[henryzz]

Originally Posted by R. Gerbicz

For that record used only your 1st method with the following modification:
collect in array/vector those res values that occur maximal times as x%p and choose randomly(!) one res value from these. It gives some breath for the algorithm, but notice that you can stuck in a local min, so without several restarts you could be far from global min. I'd say the above result is not very far from optimal, but this is just my guess.

I think there are a few approaches to this.
I think you are suggesting randomly pick one that matches the res in question, randomize the others and then optimize everything using the previously defined methods.

Depending on how many primes hit the chosen res value it may be possible to do an exhaustive search for all of them(not certain but I think 10-15 would be possible). This would have the greatest chance of success I think.

I think an obvious optimization for this would be to recognize that there will be some very small primes that don't stand a chance of being changed. The sieve array could also be pre-populated with the sieve for all the other primes.

Local minima have the potential to be an issue. I need to try again with random starting points rather than just zeros. Selecting subsets that have more potential to improve to randomize seems like a decent way forward. Some form of simulated annealing might be sensible although I am not sure how to apply it in this case.

[henryzz]

@CraigLo How are you working out your probabilities? The obvious calculation is to sum the probabilities for each start point x < 0 that a gap >=xx merit starts there. However, these probabilities don't strike me as independent so summing them wouldn't be correct.

I assume that this calculation is always going to be too slow to optimize based on this.

[CraigLo]

Originally Posted by henryzz

@CraigLo How are you working out your probabilities? The obvious calculation is to sum the probabilities for each start point x < 0 that a gap >=xx merit starts there. However, these probabilities don't strike me as independent so summing them wouldn't be correct.

I assume that this calculation is always going to be too slow to optimize based on this.

1. Calculate the probability that a gap >= G starts at the first point < 0.
2. Calculate the probability that a gap >= G starts at the second point < 0. A gap starting here will also include the first point so add this to the probability for the first point as well.
3. Calculate the probability that a gap >= G starts at the third point < 0. A gap starting here will also include the first and second points so add this to the probability for the first two as well.
4. Continue this for all points < 0.


When you are finished we have the probability that a point is included in a gap >= G. Every gap will include the first point. A gap will include a point at G/2 only about half the time so sieving a point at G/2 is only half as helpful as sieving a point at 0. A gap will only include a point at 3G/4 about 1/10th the time so sieving a point here is only 1/10th as helpful as sieving a point at 0.


The probabilities calculated above will change depending on the offset chosen but I think the changes will be small enough that they can be ignored. With this assumption the probabilities can be pre-computed and the optimization problem is similar to the one you are already doing.


You are currently subtracting 1 for each element sieved in the interval -G/2 to G/2 and 0 outside this region and minimizing the result.


I am suggesting we subtract the pre-computed probability for each element sieved over the interval -G to G and minimize this.

[henryzz]

I have finally had time to code swapping based on probabilities of offsets being included in a gap. I have based it on the raw probabilities before accounting for offsets. I am unsure whether I need to change that although I am not sure how I would best do that as calculating the probabilities is not fast the way I am currently doing it.

This turned up the solution for a range of 220k and 440k::

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 16 32 3729 3789 0 128 4 3705 0 0 3837 0 0 0 3377 256 3879 64 3915 0 0 0 3687 0 0 0 0 0 512 0 2 0 4025 1024 0 0 0 3055 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2048 0 0 0 0 0 0 0 0 0 0 0 2471 0 0 0 4096 0 0 495 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2365 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1613 0 0 0 0 3942 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1259 0 0 1277 5052 1493 0 5100 0 0 0 0 1273 0 0 1417 5004 1279 0 5364 1309 5112 5256 1547 1145 5244 1339 0 5460 5460 1589 5256 1477 0 0 5160 5460 0 1445 1355 1177 0 0 5556 0 5244 0 0 5400 0 0 5424 0 5544 0 0 0 0 0 0 0 0 0 0 0 0 1975 4920 0 0 0 0 0 4776 0 4884 2215 0 0 0 2047 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4709 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5423 0 0 5729 0 0 5095 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3787 0 0 4104 0 0 0 0 0 0 0 0 0 0 0

I am a little concerned that this pushes the average gap size rather than the probability of a large gap. How does this perform for the stats in post #9?

[CraigLo]

Sorry, I was away for a few days. Can you post the CRT number? I was using this for computing the stats.