CRT offsets

[Bobby Jacobs]

Very neat! What does the sequence of numbers at the bottom mean?

1, 2, 4, 1, 1, 4, 0, 0, 0, 0, ...

[henryzz]

Originally Posted by Bobby Jacobs

Very neat! What does the sequence of numbers at the bottom mean?

1, 2, 4, 1, 1, 4, 0, 0, 0, 0, ...

The offset is 1 mod 2, 2 mod 3, 4 mod 5 etc for primes up to 7993

[mart_r]

I've found a couple of gaps for the list.
Option 1) Submitting the full numbers with about 3420 digits each
Option 2) Submitting the numbers in the shortened form m*p#/d-x, but then they would still have > 1600 characters each
Option 3) I post the two CRT offset numbers c and corresponding m here, where the gap offsets would then be = m*7963#+c

Which option is best?

[CraigLo]

Originally Posted by mart_r

I've found a couple of gaps for the list.
Option 1) Submitting the full numbers with about 3420 digits each
Option 2) Submitting the numbers in the shortened form m*p#/d-x, but then they would still have > 1600 characters each
Option 3) I post the two CRT offset numbers c and corresponding m here, where the gap offsets would then be = m*7963#+c

Which option is best?

Option 1 is easiest for me but I could probably handle any of them.


What approach did you use for finding the offsets?

[CraigLo]

Originally Posted by henryzz

Sorry, I thought I had posted that. I have added a couple more attempts that I hope should be better. They optimize for gaps of 20 and 15 merit. These attempts have much fewer deviations from a CRT of 0.

         Max          15/20
20    8.16E-08    8.92E-04
21    2.28E-08    5.11E-04
22    6.29E-09    2.89E-04
23    1.72E-09    1.61E-04
24    4.70E-10    8.87E-05
25    1.27E-10    4.83E-05
26    3.43E-11    2.60E-05
27    9.21E-12    1.39E-05
28    2.47E-12    7.30E-06
29    6.59E-13    3.81E-06
30    1.76E-13    1.97E-06
31    4.68E-14    1.01E-06
32    1.25E-14    5.11E-07
33    3.31E-15    2.57E-07
34    8.79E-16    1.28E-07
35    2.33E-16    6.35E-08
36    6.20E-17    3.12E-08
37    1.64E-17    1.52E-08
38    4.35E-18    7.31E-09
39    1.15E-18    3.49E-09
40    3.04E-19    1.65E-09

Something seems to have gone wrong with the max gap optimized case. It is several orders of magnitude worse. The 15 and 20 cases are mirror images of one another and give the same results. They are the new best results for merit=25 to 38.

[mart_r]

Originally Posted by CraigLo

Option 1 is easiest for me but I could probably handle any of them.

What approach did you use for finding the offsets?

The cloudygo page doesn't seem to like such big numbers, so I attached them here (format: gap merit prime_start).

I took one of Raph's Henry's offsets, discarded the factor 7993 (i.e. offset mod 7963#) and let Pari have a go at it for a day or two. Hoped to hit one of the first missing gaps, but no luck there.
If needed, I also have this Pari one-liner to turn a list of CRT offsets into a number o (mod p#), with input r as a vector:

r=readvec("offset_res.txt");o=0;p=1;q=1;for(i=1,#r,q=nextprime(q+1);o=o+((q-(r[i]+o)%q)*bezout(p%q,q)[1])%q*p;p=p*q);print(o)

[CraigLo]

Are those all new records? Sorry, I thought you had some new CRT offsets you wanted me to look at.

[mart_r]

Last time I checked, and that was the day before yesterday, these were 18 improvements in merit and 3 new entries.

[henryzz]

Originally Posted by CraigLo

         Max          15/20
20    8.16E-08    8.92E-04
21    2.28E-08    5.11E-04
22    6.29E-09    2.89E-04
23    1.72E-09    1.61E-04
24    4.70E-10    8.87E-05
25    1.27E-10    4.83E-05
26    3.43E-11    2.60E-05
27    9.21E-12    1.39E-05
28    2.47E-12    7.30E-06
29    6.59E-13    3.81E-06
30    1.76E-13    1.97E-06
31    4.68E-14    1.01E-06
32    1.25E-14    5.11E-07
33    3.31E-15    2.57E-07
34    8.79E-16    1.28E-07
35    2.33E-16    6.35E-08
36    6.20E-17    3.12E-08
37    1.64E-17    1.52E-08
38    4.35E-18    7.31E-09
39    1.15E-18    3.49E-09
40    3.04E-19    1.65E-09

Something seems to have gone wrong with the max gap optimized case. It is several orders of magnitude worse. The 15 and 20 cases are mirror images of one another and give the same results. They are the new best results for merit=25 to 38.

Just realized I never responded to this.
I think it makes sense that the average gap case would be bad. It punishes central candidates so strongly it ignores wider candidates. I would imagine for extremely low merit it would be excellent.
I am a little confused by why 15 and 20 were mirrors of each other. I suppose it makes some sense as P(gap|starting value) doesn't actually change. It is just the amount of times that they were cumulated that changed. I used old slow code for implementing probabilities as it was simpler. I think I can add this to my faster code which will allow optimizing two at once again. I also have Robert's idea to try. Time is the issue...

[CraigLo]

Originally Posted by mart_r

I took one of Raph's Henry's offsets, discarded the factor 7993 (i.e. offset mod 7963#) and let Pari have a go at it for a day or two. Hoped to hit one of the first missing gaps, but no luck there.

The CRT offsets listed in this thread so far are all improvements on 7993#/13#. These work best for merits in roughly 25-35 range. The first missing gaps are in the 15 merit range. You would probably be better off using 7993#/210 for these. A quick optimization gives 43*7993#/210. I think you will find about 50% more gaps with merit of 15 using this.

[CraigLo]

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.

The table below shows the number of candidates remaining for gaps from 20k to 440k and the probability of finding a gap>220k.

Gap Size   /13#  CRT_6776   CRT_6751   CRT_6727    OPT_15
 20000      570     530        519        476        560
 40000      907     883        871        834        891
 60000     1344    1315       1306       1288       1327
 80000     1841    1834       1832       1822       1823
100000     2386    2388       2400       2398       2372
120000     3053    3026       3020       3039       3034
140000     3744    3723       3717       3734       3727
160000     4468    4441       4435       4464       4449
180000     5227    5194       5182       5230       5205
200000     6012    5980       5962       5988       6000
220000     6850    6776       6751       6727       6840
240000     7703    7717       7709       7738       7694
260000     8591    8626       8639       8748       8583
280000     9472    9560       9599       9768       9461
300000    10411   10530      10593      10804      10407
320000    11357   11511      11589      11856      11358
340000    12329   12507      12601      12906      12335
360000    13306   13522      13636      13988      13317
380000    14303   14528      14662      15075      14320
400000    15319   15584      15733      16154      15342
420000    16344   16657      16821      17268      16372
440000    17391   17716      17894      18390      17423

prob > 220000
       7.13E-06  6.92E-06   6.83E-06    5.99E-06   7.30E-06

Focusing on 6727, it has the fewest remaining candidates from 0-80k. It is a little worse than average from 100k-200k. It is best at 220k. Above 220k it has by far the most remaining candidates. The tradeoff seems to have been fewer candidates in the first 220k for far more candidates outside this region. This resulted in worse performance overall. There seems to have been a similar tradeoff for the other CRTs though it was much less extreme.