CRT offsets

[henryzz]

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.

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.

[henryzz]

I thought it might be useful for me to share my algorithms for optimizing the offsets for one or two primes. Any improvements or questions would be appreciated.

Algorithm for optimizing one prime at once:

1. Calculate current score
2. Choose a prime p to investigate
3. Generate the sieve array ignoring the prime p
4. Loop through sieve array. If the element is set then increment the value for x % p to count how many times that modulus occurs. As we are iterating subtraction can be used rather than division to maintain speed.
5. Choose the modulus with the maximum number of occurrences.
6. Return to step 2 and choose the next prime

Algorithm for optimizing two primes at once:

1. Calculate current score
2. Choose a prime p to investigate
3. Choose a candidate offset for the prime p
4. Calculate a score with the offset chosen in step 3. Record the difference between this and the best score. This difference is the improvement needed by the second prime.
5. Choose a prime q > p to investigate
6. Generate the sieve array ignoring the prime q
7. Loop through sieve array. If the element is set then increment the value for x % q to count how many times that modulus occurs. As we are iterating subtraction can be used rather than division to maintain speed.
8. Check if the modulus with the maximum number of occurrences improves the score enough to correct for the offset chosen in step 3(that was probably worse than the best). If so keep it.
9. Return to step 5 and choose the next prime unless all have been tried
9. Return to step 3 and choose the next offset unless all offsets have been tried
10. Return to step 2 and choose the next prime

[mart_r]

These are some exciting news!
I'm going to do some tests with the numbers in the coming days.

[henryzz]

I have discovered that my code for optimizing two primes at once never ran in that example.

A new solution with a score of 6751 which is a 1.85% reduction:

CRT: 8469576951389608151420874612615248616679698628057854437509053972612955366555320894561872624382237635079885558563870534052217477436104252867174000041944156922912561766571997613006274021838826098197325662350934223350741723829453060156074421445837208255551556476810588934325648951128820567850687481042537296586478777428454819368501658137716248939703709052207615032122029068361490990563292657505826840688262675440573949681785688562184745930464202386467618022726533740660243190799332773437399842946158833982674676425510200684032568143951671293691370321799819336716700358907545429943530422898407791341511921681314446274773327602900320481956968946843797282682574932894684966040924977143304891767716524218522224936463951014999066477878268171275264707709149431832902561928496148592689848474046162851289479187235111656666213839360392289731861241239720808886029056558521388726512874800370512496880793187880924543820118420840145398615041449704391530784132285244099094179856336900303772721468723679779063627069841459985611913686007421021243652404760798171849403655737475138373549743888443864575288425141105161547963150705121654884290994510253244670208557545985000235032372142518137921512941385589556622276085201236169381606533374179244088628404687835948161844272649862634525800077115357854869915899243762608571034327460038871807559461325957221993127284885145386256067988154853447758014361607999698831259504448329042743089130220831200489088887537838750681387087767022701182626524696926458762623129955177683776233366828778342669184487734636570942685311644027753361053450100749345467048948865209261963820137122554115571221339740099583465185411253888270073588498091981787259244906051673644422452596024426500938487129453252645374507942343995126219107225573379784056315868057346232635860997414098016376029573942170734698751505396133782438672809906699219815739263597462525293228996396324160649240961334834847630260552990397264236203563967578703243898637175343089911074500785618183264451868946154512867798070635093405106622945892148665297395754589653740283735911128979800063785478611407363085180586031749390310708165010716505502352043889672055641034853846639815491476733852947674830142758738340739713317166255073384485662593989473604750482708526620508676929131092773723611139952568902506370068713560887716229793234977719976539390718331237488896298963758648587199452808298507103139928999916636620120946467017007745896989025950050891299944364458128718199522075512823093943125147828933774814684579625127285057613564486948473575018389753837523630779976784430768308097266761592607807793095521726619861464426048736379270150434607863399056390508683087224846655375799136157533277970790907876341451083224572991331610888258518518910406592214153325486473654621570104732800693060638149475785478579287985467321570059015938495293761530426109736573097235202893030745098214278835496858156318531446429216802142654019627757560352495360637123367043006265244002462352550828844394477047298735623303654397493154092689404708886131824996652784745146417777652008770799504658114793560731473454734217047847792687746815566476473161282366702298904860480598385581466291458096839125454749809204220298893707965248295603648219182839069213492098305733841698267716224826531076751266302888478535140828022311245755299925807313340739971476323322672142330110864171788382566255008478431410933741077804609620498830400767753967830750382506079963878400826435518792682438473813491299
Score: 6751 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 1744 0 0 0 0 0 0 2893 0 0 0 0 0 0 0 0 0 0 0 1634 0 0 0 0 0 0 0 0 0 0 235 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 638 0 0 0 5017 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5270 0 0 0 4581 1541 0 0 0 0 0 0 0 0 2872 0 0 0 0 0 0 0 3520 0 0 0 0 727 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4407 0 0 0 0 0 1330 0 0 0 2258 0 5939 0 0 0 0 0 726 0 0 0 0 4981 4388 0 371 0 3057 3423 0 4634 6119 0 0 775 0 0 378 0 0 0 2646 1350 0 0 0 0 5471 0 1805 0 0 836 1170 0 4683 0 0 0 0 0 0 3456 530 954 0 4405 0 858 3325 0 0 0 3002 0 0 690 3601 0 0 6003 0 0 0 450 2594 0 0 0 0 910 3955 5094 0 0 0 0 2185 0 6479 0 0 0 4089 0 5661 0 0 0 0 0 4493 1832 0 0 1567 0 0 4977 0 4057 0 3682 2514 0 0 0 0 6370 0 0 0 0 0 2268 0 1851 216 0 6194 5711 0 316 6248 1476 3693 892 0 6250 0 0 0 0 0 3850 7204 0 5047 0 0 1512 3954 596 95 0 4028 5252 0 3548 0 7488 1459 0 0 0 0 0 0 392 2338 0 0 1744 6526 0 0 0 2903 0 599 2963 5057 359 0 6714 0 0 0 0 0 0 0 0 2330 0 0 5040 2711 4294 0 0 5880 29 5315 0 0 0 6623 4980 6269 6750 4105 2147 4337 4503 0 5760 6086

[Nick]

What's your PhD thesis about?

[henryzz]

Originally Posted by Nick

What's your PhD thesis about?

My title is: How do dynamic changes in risk factors impact outcomes in patients with atrial fibrillation?

[Nick]

Originally Posted by henryzz

My title is: How do dynamic changes in risk factors impact outcomes in patients with atrial fibrillation?

Sounds good! We have a cardiologist in the family so occasionally get a layman's update on developments.

[R. Gerbicz]

Originally Posted by henryzz

I have discovered that my code for optimizing two primes at once never ran in that example.

A new solution with a score of 6751 which is a 1.85% reduction:

CRT: 8469576951389608151420874612615248616679698628057854437509053972612955366555320894561872624382237635079885558563870534052217477436104252867174000041944156922912561766571997613006274021838826098197325662350934223350741723829453060156074421445837208255551556476810588934325648951128820567850687481042537296586478777428454819368501658137716248939703709052207615032122029068361490990563292657505826840688262675440573949681785688562184745930464202386467618022726533740660243190799332773437399842946158833982674676425510200684032568143951671293691370321799819336716700358907545429943530422898407791341511921681314446274773327602900320481956968946843797282682574932894684966040924977143304891767716524218522224936463951014999066477878268171275264707709149431832902561928496148592689848474046162851289479187235111656666213839360392289731861241239720808886029056558521388726512874800370512496880793187880924543820118420840145398615041449704391530784132285244099094179856336900303772721468723679779063627069841459985611913686007421021243652404760798171849403655737475138373549743888443864575288425141105161547963150705121654884290994510253244670208557545985000235032372142518137921512941385589556622276085201236169381606533374179244088628404687835948161844272649862634525800077115357854869915899243762608571034327460038871807559461325957221993127284885145386256067988154853447758014361607999698831259504448329042743089130220831200489088887537838750681387087767022701182626524696926458762623129955177683776233366828778342669184487734636570942685311644027753361053450100749345467048948865209261963820137122554115571221339740099583465185411253888270073588498091981787259244906051673644422452596024426500938487129453252645374507942343995126219107225573379784056315868057346232635860997414098016376029573942170734698751505396133782438672809906699219815739263597462525293228996396324160649240961334834847630260552990397264236203563967578703243898637175343089911074500785618183264451868946154512867798070635093405106622945892148665297395754589653740283735911128979800063785478611407363085180586031749390310708165010716505502352043889672055641034853846639815491476733852947674830142758738340739713317166255073384485662593989473604750482708526620508676929131092773723611139952568902506370068713560887716229793234977719976539390718331237488896298963758648587199452808298507103139928999916636620120946467017007745896989025950050891299944364458128718199522075512823093943125147828933774814684579625127285057613564486948473575018389753837523630779976784430768308097266761592607807793095521726619861464426048736379270150434607863399056390508683087224846655375799136157533277970790907876341451083224572991331610888258518518910406592214153325486473654621570104732800693060638149475785478579287985467321570059015938495293761530426109736573097235202893030745098214278835496858156318531446429216802142654019627757560352495360637123367043006265244002462352550828844394477047298735623303654397493154092689404708886131824996652784745146417777652008770799504658114793560731473454734217047847792687746815566476473161282366702298904860480598385581466291458096839125454749809204220298893707965248295603648219182839069213492098305733841698267716224826531076751266302888478535140828022311245755299925807313340739971476323322672142330110864171788382566255008478431410933741077804609620498830400767753967830750382506079963878400826435518792682438473813491299
Score: 6751 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 1744 0 0 0 0 0 0 2893 0 0 0 0 0 0 0 0 0 0 0 1634 0 0 0 0 0 0 0 0 0 0 235 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 638 0 0 0 5017 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5270 0 0 0 4581 1541 0 0 0 0 0 0 0 0 2872 0 0 0 0 0 0 0 3520 0 0 0 0 727 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4407 0 0 0 0 0 1330 0 0 0 2258 0 5939 0 0 0 0 0 726 0 0 0 0 4981 4388 0 371 0 3057 3423 0 4634 6119 0 0 775 0 0 378 0 0 0 2646 1350 0 0 0 0 5471 0 1805 0 0 836 1170 0 4683 0 0 0 0 0 0 3456 530 954 0 4405 0 858 3325 0 0 0 3002 0 0 690 3601 0 0 6003 0 0 0 450 2594 0 0 0 0 910 3955 5094 0 0 0 0 2185 0 6479 0 0 0 4089 0 5661 0 0 0 0 0 4493 1832 0 0 1567 0 0 4977 0 4057 0 3682 2514 0 0 0 0 6370 0 0 0 0 0 2268 0 1851 216 0 6194 5711 0 316 6248 1476 3693 892 0 6250 0 0 0 0 0 3850 7204 0 5047 0 0 1512 3954 596 95 0 4028 5252 0 3548 0 7488 1459 0 0 0 0 0 0 392 2338 0 0 1744 6526 0 0 0 2903 0 599 2963 5057 359 0 6714 0 0 0 0 0 0 0 0 2330 0 0 5040 2711 4294 0 0 5880 29 5315 0 0 0 6623 4980 6269 6750 4105 2147 4337 4503 0 5760 6086

Improved solution with 6727 numbers survived the sieve:

c=894101235464362219721356880526656966576862269828154398514501227439505880868173768034261872450219940738532433503702992181332283540241729189200170368496080770122489627384936785180822077759420834840561182525045255938041478030429899220789025231018470726274025492966577222895730338530292884911304277977699222206813826083925528607407799301583580289812608633646270306158259174036079292088947790819460085862530772370455045076770278964550649084460021280341711965062751491000554253170673646713078344136774647836997201604339266315692210513549633580358609336259645730281936246594603456661570776888550674163634855633831796384828091280700810908752015094038200535425967302545438000348218598245332367415689514556533807924323611251898728570083748171206589525074279586797457698429254606804258189533651817045728718393452270759924592675278463371210308241363761870425698856921072227432679151112064523990764452715478267958012714547443885201030528280178023966939575884538466086574843776408189417837812055471550930523625276363727449113222586477779002040574021717468505417530151198648354820236809644181741987407621291156982412248712010181628887088591618292913355828004228067420111435043157992659197693679697297306193268946853228042239659270956989976808964040163253787225672984728295075589585376728012746179310829710199392901875388666410598686890175601525712229638029608005550169463504405962647786956288427048281930470726811599112235540649761269587349639189410143432348745718604409679652174797058300364683985530000911456959333788684229582059305261022598796234510678710978630229142737943627091943012769300825635516414744818796511477636303583986805007029374735816223473972159595733842011861521954425026119396159574670408544104665751951696384669678102450544493505977567652253124724792572488023495857586056491430481170106603895295280433201526704050258004779142094368127356640032572152055880400956480991671714157419673844216327291996287985774765949788048994117868350791991047293406031640441655409535734211716075143902785171452558689018612296071330944599380563622304728360830364074129032435888551988219490433326856557423715492247871137512878245840634216466637848940266182444735750086742889766031619666311820633684286973774359628034404401583508236488898646822505365046407238113673259344652677158165745036109887829163563567646520223972380464316042166790790693114352428388364722769592005875489209496529405691053910434076264528443715278874328439894657327238467248337101747689678283984347139861551539594013177790624611325080205297391833388427498485470668802506635522617306598874661249298098297526692019854328905349621621861481661734112299946598507185699362243478831896469919744277949661645477466251371546539398053977019979598064776590532404410742950596859290942940124276493228074685653408594265857311993997836469900025326597722719858380729151183108607568446547277547008273121775991099397711796734842892790807406332936630945708209528554119434233296421185811055765457485357326882091683943278438330731574590639585492816854036436053779656789420982313131475910956271639570875455598599104813291692484667526552908981818701580919007911469447297251959275472417184201256584879618163132293893374351565916952074567060529507006270580469479405330364937727713703898012119701295575478573459984224904343045725473505704190646951312484991894044407080091394692206526715577671509672870081507785250017047593209776248063781170242589849299138314228397347311816225505996337124551829;
t=1;forprime(p=2,7993,t*=p)   
sum(i=-110000,110000,gcd(c+i,t)==1)
%45 = 6727

[CraigLo]

Nice work on the CRTs.

If you are looking for a gap of 220k then the first prime can range from -220k to 0 and the second prime can range from 0 to 220k. If you want to maximize your chance of finding a gap of 220k you probably want to run your CRT code for a gap size larger than 220k.

220k is roughly a merit of 28. I have a code that will calculate the probability of finding a gap greater than a given merit for a primorial and offset. I ran it for the 3 CRTs above and /7#, /11#, /13#, /17#.

Merit     CRT_6776    CRT_6751    CRT_6727    7993#/7#    7993#/11#_1 7993#/11#_13 7993#/13#   7993#/17#
20        8.99E-04    9.10E-04    8.77E-04    1.00E-03    1.03E-03    9.97E-04     8.20E-04    6.18E-04
21        5.13E-04    5.19E-04    4.96E-04    5.35E-04    5.73E-04    5.56E-04     4.70E-04    3.56E-04
22        2.89E-04    2.92E-04    2.76E-04    2.80E-04    3.15E-04    3.05E-04     2.65E-04    2.03E-04
23        1.60E-04    1.61E-04    1.52E-04    1.44E-04    1.71E-04    1.65E-04     1.48E-04    1.14E-04
24        8.76E-05    8.80E-05    8.17E-05    7.28E-05    9.13E-05    8.80E-05     8.15E-05    6.35E-05
25        4.73E-05    4.74E-05    4.34E-05    3.63E-05    4.81E-05    4.64E-05     4.44E-05    3.51E-05
26        2.52E-05    2.52E-05    2.27E-05    1.79E-05    2.51E-05    2.41E-05     2.39E-05    1.92E-05
27        1.33E-05    1.32E-05    1.17E-05    8.66E-06    1.29E-05    1.24E-05     1.28E-05    1.04E-05
28        6.92E-06    6.83E-06    5.99E-06    4.15E-06    6.56E-06    6.30E-06     6.73E-06    5.56E-06
29        3.57E-06    3.49E-06    3.01E-06    1.96E-06    3.30E-06    3.17E-06     3.51E-06    2.96E-06
30        1.82E-06    1.76E-06    1.49E-06    9.17E-07    1.64E-06    1.57E-06     1.82E-06    1.56E-06
31        9.16E-07    8.82E-07    7.23E-07    4.25E-07    8.08E-07    7.75E-07     9.34E-07    8.17E-07
32        4.57E-07    4.36E-07    3.48E-07    1.94E-07    3.94E-07    3.78E-07     4.75E-07    4.24E-07
33        2.26E-07    2.13E-07    1.65E-07    8.80E-08    1.90E-07    1.83E-07     2.40E-07    2.19E-07
34        1.11E-07    1.04E-07    7.79E-08    3.95E-08    9.12E-08    8.75E-08     1.20E-07    1.12E-07
35        5.38E-08    4.97E-08    3.63E-08    1.76E-08    4.33E-08    4.15E-08     5.95E-08    5.68E-08
36        2.59E-08    2.37E-08    1.68E-08    7.76E-09    2.04E-08    1.96E-08     2.93E-08    2.87E-08
37        1.24E-08    1.12E-08    7.67E-09    3.40E-09    9.51E-09    9.13E-09     1.43E-08    1.44E-08
38        5.87E-09    5.23E-09    3.48E-09    1.47E-09    4.40E-09    4.22E-09     6.94E-09    7.13E-09
39        2.75E-09    2.43E-09    1.57E-09    6.34E-10    2.01E-09    1.94E-09     3.33E-09    3.51E-09
40        1.27E-09    1.11E-09    6.96E-10    2.69E-10    9.11E-10    8.76E-10     1.58E-09    1.70E-09

CRT_6776 is better than CRT_6751 for merits > 26. CRT_6727 is worse than the other 2 CRTs for all merits (it might be better for some cases below 20).

7993#/7# is best below 20
7993#/11# is best from 20-26
CRT_6776 is best from 26-30
7993#/13# is best from 30-37
7993#/17# is best above 37

The /Q# cases were computed with A mod Q# = 1 but there is some variation among the offset chosen. For /11# I ran for offsets 1 and 13 which were one of the best and worst cases. The offset of 1 gives about a 4% improvement over 13.

[henryzz]

Originally Posted by R. Gerbicz

Improved solution with 6727 numbers survived the sieve:

c=894101235464362219721356880526656966576862269828154398514501227439505880868173768034261872450219940738532433503702992181332283540241729189200170368496080770122489627384936785180822077759420834840561182525045255938041478030429899220789025231018470726274025492966577222895730338530292884911304277977699222206813826083925528607407799301583580289812608633646270306158259174036079292088947790819460085862530772370455045076770278964550649084460021280341711965062751491000554253170673646713078344136774647836997201604339266315692210513549633580358609336259645730281936246594603456661570776888550674163634855633831796384828091280700810908752015094038200535425967302545438000348218598245332367415689514556533807924323611251898728570083748171206589525074279586797457698429254606804258189533651817045728718393452270759924592675278463371210308241363761870425698856921072227432679151112064523990764452715478267958012714547443885201030528280178023966939575884538466086574843776408189417837812055471550930523625276363727449113222586477779002040574021717468505417530151198648354820236809644181741987407621291156982412248712010181628887088591618292913355828004228067420111435043157992659197693679697297306193268946853228042239659270956989976808964040163253787225672984728295075589585376728012746179310829710199392901875388666410598686890175601525712229638029608005550169463504405962647786956288427048281930470726811599112235540649761269587349639189410143432348745718604409679652174797058300364683985530000911456959333788684229582059305261022598796234510678710978630229142737943627091943012769300825635516414744818796511477636303583986805007029374735816223473972159595733842011861521954425026119396159574670408544104665751951696384669678102450544493505977567652253124724792572488023495857586056491430481170106603895295280433201526704050258004779142094368127356640032572152055880400956480991671714157419673844216327291996287985774765949788048994117868350791991047293406031640441655409535734211716075143902785171452558689018612296071330944599380563622304728360830364074129032435888551988219490433326856557423715492247871137512878245840634216466637848940266182444735750086742889766031619666311820633684286973774359628034404401583508236488898646822505365046407238113673259344652677158165745036109887829163563567646520223972380464316042166790790693114352428388364722769592005875489209496529405691053910434076264528443715278874328439894657327238467248337101747689678283984347139861551539594013177790624611325080205297391833388427498485470668802506635522617306598874661249298098297526692019854328905349621621861481661734112299946598507185699362243478831896469919744277949661645477466251371546539398053977019979598064776590532404410742950596859290942940124276493228074685653408594265857311993997836469900025326597722719858380729151183108607568446547277547008273121775991099397711796734842892790807406332936630945708209528554119434233296421185811055765457485357326882091683943278438330731574590639585492816854036436053779656789420982313131475910956271639570875455598599104813291692484667526552908981818701580919007911469447297251959275472417184201256584879618163132293893374351565916952074567060529507006270580469479405330364937727713703898012119701295575478573459984224904343045725473505704190646951312484991894044407080091394692206526715577671509672870081507785250017047593209776248063781170242589849299138314228397347311816225505996337124551829;
t=1;forprime(p=2,7993,t*=p)   
sum(i=-110000,110000,gcd(c+i,t)==1)
%45 = 6727

That's a nice improvement. How did you find this?

Originally Posted by CraigLo

Nice work on the CRTs.

If you are looking for a gap of 220k then the first prime can range from -220k to 0 and the second prime can range from 0 to 220k. If you want to maximize your chance of finding a gap of 220k you probably want to run your CRT code for a gap size larger than 220k.

220k is roughly a merit of 28. I have a code that will calculate the probability of finding a gap greater than a given merit for a primorial and offset. I ran it for the 3 CRTs above and /7#, /11#, /13#, /17#.

Merit     CRT_6776    CRT_6751    CRT_6727    7993#/7#    7993#/11#_1 7993#/11#_13 7993#/13#   7993#/17#
20        8.99E-04    9.10E-04    8.77E-04    1.00E-03    1.03E-03    9.97E-04     8.20E-04    6.18E-04
21        5.13E-04    5.19E-04    4.96E-04    5.35E-04    5.73E-04    5.56E-04     4.70E-04    3.56E-04
22        2.89E-04    2.92E-04    2.76E-04    2.80E-04    3.15E-04    3.05E-04     2.65E-04    2.03E-04
23        1.60E-04    1.61E-04    1.52E-04    1.44E-04    1.71E-04    1.65E-04     1.48E-04    1.14E-04
24        8.76E-05    8.80E-05    8.17E-05    7.28E-05    9.13E-05    8.80E-05     8.15E-05    6.35E-05
25        4.73E-05    4.74E-05    4.34E-05    3.63E-05    4.81E-05    4.64E-05     4.44E-05    3.51E-05
26        2.52E-05    2.52E-05    2.27E-05    1.79E-05    2.51E-05    2.41E-05     2.39E-05    1.92E-05
27        1.33E-05    1.32E-05    1.17E-05    8.66E-06    1.29E-05    1.24E-05     1.28E-05    1.04E-05
28        6.92E-06    6.83E-06    5.99E-06    4.15E-06    6.56E-06    6.30E-06     6.73E-06    5.56E-06
29        3.57E-06    3.49E-06    3.01E-06    1.96E-06    3.30E-06    3.17E-06     3.51E-06    2.96E-06
30        1.82E-06    1.76E-06    1.49E-06    9.17E-07    1.64E-06    1.57E-06     1.82E-06    1.56E-06
31        9.16E-07    8.82E-07    7.23E-07    4.25E-07    8.08E-07    7.75E-07     9.34E-07    8.17E-07
32        4.57E-07    4.36E-07    3.48E-07    1.94E-07    3.94E-07    3.78E-07     4.75E-07    4.24E-07
33        2.26E-07    2.13E-07    1.65E-07    8.80E-08    1.90E-07    1.83E-07     2.40E-07    2.19E-07
34        1.11E-07    1.04E-07    7.79E-08    3.95E-08    9.12E-08    8.75E-08     1.20E-07    1.12E-07
35        5.38E-08    4.97E-08    3.63E-08    1.76E-08    4.33E-08    4.15E-08     5.95E-08    5.68E-08
36        2.59E-08    2.37E-08    1.68E-08    7.76E-09    2.04E-08    1.96E-08     2.93E-08    2.87E-08
37        1.24E-08    1.12E-08    7.67E-09    3.40E-09    9.51E-09    9.13E-09     1.43E-08    1.44E-08
38        5.87E-09    5.23E-09    3.48E-09    1.47E-09    4.40E-09    4.22E-09     6.94E-09    7.13E-09
39        2.75E-09    2.43E-09    1.57E-09    6.34E-10    2.01E-09    1.94E-09     3.33E-09    3.51E-09
40        1.27E-09    1.11E-09    6.96E-10    2.69E-10    9.11E-10    8.76E-10     1.58E-09    1.70E-09

CRT_6776 is better than CRT_6751 for merits > 26. CRT_6727 is worse than the other 2 CRTs for all merits (it might be better for some cases below 20).

7993#/7# is best below 20
7993#/11# is best from 20-26
CRT_6776 is best from 26-30
7993#/13# is best from 30-37
7993#/17# is best above 37

The /Q# cases were computed with A mod Q# = 1 but there is some variation among the offset chosen. For /11# I ran for offsets 1 and 13 which were one of the best and worst cases. The offset of 1 gives about a 4% improvement over 13.

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

[R. Gerbicz]

Originally Posted by henryzz

That's a nice improvement. How did you find this?

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.

Originally Posted by henryzz

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

Yeah, use it if you'd want to reach say merit=25, use a larger gap for merit=30. Ofcourse we don't know in advance what merits you will get in a search, but using this gap for merit=40 isn't that useful/optimal.