Thread: CRT offsets
View Single Post
Old 2021-04-05, 13:22   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

61·97 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Improved solution with 6727 numbers survived the sieve:
Code:
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?

Quote:
Originally Posted by CraigLo View Post
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#.
Code:
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.
henryzz is offline   Reply With Quote