Thread: CRT offsets
View Single Post
Old 2021-04-01, 15:36   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

10111001000002 Posts
Default CRT offsets

In the past using CRT offsets has been considered as an alternative to using a divisor to reduce the density of candidates after sieving. This had some success with small primorials but struggled with larger primorials due to good CRT offsets being difficult to find. We used a program written by ATH last updated https://www.mersenneforum.org/showpo...&postcount=117. For small primorials this did an exhaustive search but for larger primorials this was impossible and it used a combination of random selection and exhaustive search on the largest primes.

I have written a program that uses an alternative approach. It starts with zero offsets for all primes and then iterates through the primes trying all the possible offsets for each prime. My program will also iterate through pairs of primes optimising offsets. Iterating through sets of 3 or 4 primes at once is implemented but is impractical currently for primorials large enough for them to be useful.

An example CRT offset:
For 7993# the divisor of 13# or 17# are optimal with 6880 and 6878 candidates remaining after sieving to 7993 for a gap of 220k centred on 7993#/13# or 7993#/17#.

The following CRT offset has only 6776 candidates remaining for a gap of 220k centred at 7993# + c after sieving to 7993. This is ~98.5% of the candidates. I have also included the list of offsets for each prime.
Code:
CRT: 395007274228351459553183480814210304561462006956043002044284607192704293604742948211229732571944450247353270732937057373038932455317468336527937093950721160044522551604825044039755533265288121243375824457387463267662200129904300734637548186676705352895677333521072262682798081725428878436132827656964015089346477767975843844383645002312622341316759995323885236854402079078812803869846008166897096653643718850060298351574793121082949994999516341436587255050414146654455486849854109479424428696744179086906283784721519349081386221052646423622261748308694553765825449651890759252895968991280297465788080714632023008211159515760650489163672998592315599132259440955817084803710644176335649584161510625087708437974446841593752766719720839518178794558238030404974937323408646422006972184469674025712684624945081240371165528889081982607418944912982396453918161126867151794682630721964577474090210447700010925494578725014856790806265873258167154284701003712736904273653204573586832976552273698797572852950010547691733387790556116330633969514312717188257405529894667570330682222090219396446166786800088640777837120832121970198244436736912615098911804595608785416158761652709321107013498637640472684754389984568460058181685063958242129425571336252708194568285717816372739396659671248098525408426881540005083673958605576573621977115037729254903473739579926501619750486412399140712181049180617527641546847514233473533808147467144984131656095952761999012979617571998352575349995152407037941693139398609436458279433367243131122429419538633188976889635835336688007928786399836955568222378856808976083801210597549388811433229634091849888574168896215177548553942204904401912865606687555863122813357744590940341587078185710708456153863222187952483237612446808378430436463402839096468101665935376887312148855012274064758514514915823153798828301613933440404381341662051498923986129617221165564775020153087212378889644883232378730133173914427079294999000515111535461120391085852732624081908048520122987004074535592331304730038221432596115380914543846879737531688241376162869423895956046582086917578239238958447007620989532333398332261907793383037500910466789105346668598788339923297325377707277806753939937825380250594772171268857347952445985450030685305071501817604989928071828442594987371875099503445846106606049322729784026852153884102954316831745141477860651645016257994001938623365963723941835337019645625135550190560036368326235453210017151752256817383527358459870291530047091659589699129586584500100549558033838750651952761607143768310042918732275942475489324463994076129577853438942080446375200761973903165778050286777111052861134755652083452908697133656454836134345536673477612854879020045289828855475253573719103470126901946294714007833618065961761044190191547280906913973193622194665301060296432310206032819372667487053367949926477569137502653687223483336710240613366101252397736500015971495756080188126339109337642725528760616276237280550814442231841580911743049845550322803557024649114503462921978401471074983126588699573951361408207422636414022563596779568210665818796376945576067504523094686722491020455642456489916016561388952682405846852248574582023086728817560016747093860979172383532874129251800927919050156856941284704176180580121946966657075187555463279530477386631372135643670182310778579324612903987926954745334119949859223585730764810101856878707487111824478348656741831324872510443556905936376529692193060745132780669
Score: 6776 for 1 2 4 3 9 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3362 0 0 0 0 0 0 0 0 2893 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5270 0 0 0 4439 1541 0 0 0 0 0 0 0 0 2872 0 0 0 0 0 0 0 3520 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5939 0 0 0 0 0 0 0 0 0 0 4981 4388 0 371 0 0 0 0 4634 0 0 0 6209 0 0 378 0 0 0 2646 1350 0 0 0 0 5471 0 0 0 0 836 1170 0 4683 0 0 0 0 0 0 3456 530 954 0 4405 0 0 3325 0 0 0 0 0 0 690 0 0 0 0 0 0 0 450 2594 0 0 0 0 910 3955 5094 0 0 0 0 0 0 6479 0 0 0 0 0 0 0 0 0 0 0 4493 1832 0 0 4368 0 0 4977 0 4057 0 3682 2514 0 0 0 0 0 0 0 0 0 0 0 0 1851 0 0 6194 5711 0 316 6248 1476 3693 0 0 6250 0 0 0 0 0 0 7204 0 0 0 0 0 0 0 0 0 0 5252 0 3548 0 7488 0 0 0 0 0 0 0 0 2338 0 0 1744 0 0 0 0 0 0 599 0 2106 359 0 6714 0 0 0 0 0 0 0 0 2330 0 0 5040 2711 0 0 0 6 0 5315 0 0 0 6623 4980 6269 6750 4105 6794 4337 0 0 5760 6086
This ~1.5% reduction in the number of candidates doesn't seem like much but it doesn't tell the full story. On average around 1 in 160 numbers are prime after sieving at this size. To test the same range now 160^0.985=~148 tests are needed. This is a reduction of ~7.5% which is a lot more significant. Edit: Not convinced this is correct. I think it would be more like 160*0.985

I am pretty certain that I am only scratching the surface here with the CRT offsets and far better should be possible.

Unfortunately, my program is a bit of a mess and would need quite a bit of tidying up in order for me to post it. Eventually, I will tidy it up although I am quite busy with my PhD. If anyone wants any CRT offsets I can run some searches for people.

If anyone has any suggestions on how to improve these CRT offsets I would appreciate the ideas. I am considering posting this as a puzzle in the puzzles section of the forum as that will hit a wider/different audience.

Last fiddled with by henryzz on 2021-04-01 at 16:29
henryzz is online now   Reply With Quote