mersenneforum.org CRT offsets
 Register FAQ Search Today's Posts Mark Forums Read

 2021-04-25, 16:30 #23 Bobby Jacobs     May 2018 25×7 Posts Very neat! What does the sequence of numbers at the bottom mean? 1, 2, 4, 1, 1, 4, 0, 0, 0, 0, ...
2021-04-25, 19:24   #24
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

5,881 Posts

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

 2021-04-26, 16:07 #25 mart_r     Dec 2008 you know...around... 22×167 Posts 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?
2021-04-27, 19:11   #26
CraigLo

Mar 2021

2×17 Posts

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

2021-04-27, 19:36   #27
CraigLo

Mar 2021

2·17 Posts

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

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

2021-04-27, 21:03   #28
mart_r

Dec 2008
you know...around...

29C16 Posts

Quote:
 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:
Code:
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)
Attached Files
 gaps_2021-04-27.txt (70.5 KB, 39 views)

Last fiddled with by mart_r on 2021-04-27 at 21:17

 2021-04-27, 23:47 #29 CraigLo   Mar 2021 2·17 Posts Are those all new records? Sorry, I thought you had some new CRT offsets you wanted me to look at.
 2021-04-28, 08:33 #30 mart_r     Dec 2008 you know...around... 10100111002 Posts Last time I checked, and that was the day before yesterday, these were 18 improvements in merit and 3 new entries.
2021-05-02, 07:53   #31
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

5,881 Posts

Quote:
 Originally Posted by CraigLo Code:  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...

2021-05-05, 18:16   #32
CraigLo

Mar 2021

3410 Posts

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

 2021-05-05, 23:17 #33 CraigLo   Mar 2021 428 Posts 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. Code: 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.