mersenneforum.org Prime Gap Theory
 Register FAQ Search Today's Posts Mark Forums Read

 2020-11-01, 11:36 #111 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 2·3·7·137 Posts It strikes me that we are sieving the wrong dimension. In A*p#/d+x we currently sieve over x. Why don't we sieve over A? For each A we will count how many sieves over x it has survived. The As with the lowest score can then be looked at in the traditional way. Generally, we have a much larger range of A than the maximum gap size so the number of sieves should be reduced. This should mean deeper sieving.
2020-11-03, 15:46   #112
robert44444uk

Jun 2003
Oxford, UK

35658 Posts

Quote:
 Originally Posted by henryzz It strikes me that we are sieving the wrong dimension. In A*p#/d+x we currently sieve over x. Why don't we sieve over A? For each A we will count how many sieves over x it has survived. The As with the lowest score can then be looked at in the traditional way. Generally, we have a much larger range of A than the maximum gap size so the number of sieves should be reduced. This should mean deeper sieving.
Hi henryzz - generally speaking we do sieve over A in our deficient primorial searches - A is favoured when 5mod30 or 25mod30, but others also get a look in - so I tend to look at 1,5,7,11,13,17,19,23,25,and 29mod30. In terms of mod210, the best is achieved at 35mod210 and its partner 175mod210. This is quite useful when looking at very small gaps.

2020-11-04, 11:45   #113
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2×3×7×137 Posts

Quote:
 Originally Posted by robert44444uk Hi henryzz - generally speaking we do sieve over A in our deficient primorial searches - A is favoured when 5mod30 or 25mod30, but others also get a look in - so I tend to look at 1,5,7,11,13,17,19,23,25,and 29mod30. In terms of mod210, the best is achieved at 35mod210 and its partner 175mod210. This is quite useful when looking at very small gaps.
I was more thinking about fairly deep sieving rather than what is effectively a wheel sieve. I have coded a crude sieve that can do things like sieve A=1 to 1M for x=-50k to 50k up to p=100k in about 2-3 hours. Using this to find gaps for 6199#/11# currently and am finding record gaps several times faster than before. It seems to reckon that I should be using d=7# instead of 11# as a lot of the As with the least remaining seem to have 11 as a factor. I included a table below of the probability(only based on the size of the primorial and sieve depth ignoring A) of the whole 100k range not being prime at every 5 percentiles. The probability seems to drop really fast after testing the best 25% of the dataset. Probably the best use of this is to search a range far bigger than you hope to test to find the best candidates. I am currently searching in descending order.

Code:
          0%           5%          10%          15%          20%          25%          30%
1.599538e-10 4.355472e-08 3.659155e-07 4.189505e-07 1.694673e-06 2.834374e-06 1.046412e-05
35%          40%          45%          50%          55%          60%          65%
1.260456e-05 1.339614e-05 1.423743e-05 1.597335e-05 6.638588e-05 1.672100e-04 1.875974e-04
70%          75%          80%          85%          90%          95%         100%
6.385621e-04 9.265170e-04 9.913896e-04 1.035973e-03 1.078905e-03 1.138927e-03 1.744451e-03
There a few things that could improve this. Sieving deeper gives a better ordering of the candidates. Searching a larger range of candidates generally seems to find much better candidates. I suspect that given a large enough range of A you probably don't want to sieve more than 1 or 2 percent of the whole dataset as that will be the best bit.

Here are the results of a regression fit predicting the count remaining as the gcd of A and the divisor varies. 11 is the best by quite a bit and then 1, 7 and 77 are fairly close together. The fit is amazingly accurate.
Code:
Call:
lm(formula = count ~ . - 1, data = sparse[sparse\$k > 0, ])

Residuals:
Min       1Q   Median       3Q      Max
-137.862  -17.733    0.148   17.603  143.204

Coefficients:
Estimate Std. Error t value Pr(>|t|)
gcddiv1    2.029e+03  5.882e-02   34491   <2e-16 ***
gcddiv2    3.314e+03  5.882e-02   56349   <2e-16 ***
gcddiv3    2.561e+03  8.318e-02   30785   <2e-16 ***
gcddiv5    2.166e+03  1.176e-01   18411   <2e-16 ***
gcddiv6    4.361e+03  8.318e-02   52425   <2e-16 ***
gcddiv7    2.032e+03  1.441e-01   14105   <2e-16 ***
gcddiv10   3.910e+03  1.176e-01   33236   <2e-16 ***
gcddiv11   1.963e+03  1.860e-01   10554   <2e-16 ***
gcddiv14   3.765e+03  1.441e-01   26135   <2e-16 ***
gcddiv15   3.153e+03  1.664e-01   18952   <2e-16 ***
gcddiv21   2.871e+03  2.038e-01   14089   <2e-16 ***
gcddiv22   3.571e+03  1.860e-01   19199   <2e-16 ***
gcddiv30   5.100e+03  1.664e-01   30658   <2e-16 ***
gcddiv33   2.693e+03  2.630e-01   10239   <2e-16 ***
gcddiv35   2.344e+03  2.882e-01    8135   <2e-16 ***
gcddiv42   5.042e+03  2.038e-01   24743   <2e-16 ***
gcddiv55   2.216e+03  3.720e-01    5957   <2e-16 ***
gcddiv66   4.798e+03  2.631e-01   18240   <2e-16 ***
gcddiv70   4.530e+03  2.882e-01   15721   <2e-16 ***
gcddiv77   2.048e+03  4.556e-01    4495   <2e-16 ***
gcddiv105  3.678e+03  4.075e-01    9025   <2e-16 ***
gcddiv110  4.285e+03  3.720e-01   11518   <2e-16 ***
gcddiv154  4.117e+03  4.556e-01    9035   <2e-16 ***
gcddiv165  3.420e+03  5.261e-01    6500   <2e-16 ***
gcddiv210  5.921e+03  4.075e-01   14529   <2e-16 ***
gcddiv231  3.096e+03  6.443e-01    4806   <2e-16 ***
gcddiv330  5.648e+03  5.260e-01   10738   <2e-16 ***
gcddiv385  2.485e+03  9.111e-01    2728   <2e-16 ***
gcddiv462  5.580e+03  6.443e-01    8662   <2e-16 ***
gcddiv770  5.004e+03  9.111e-01    5493   <2e-16 ***
gcddiv1155 4.044e+03  1.289e+00    3138   <2e-16 ***
gcddiv2310 6.571e+03  1.290e+00    5094   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 26.81 on 999967 degrees of freedom
Multiple R-squared:  0.9999,	Adjusted R-squared:  0.9999
F-statistic: 4.568e+08 on 32 and 999967 DF,  p-value: < 2.2e-16

2020-11-04, 12:03   #114
SethTro

"Seth"
Apr 2019

32×23 Posts

Quote:
 Originally Posted by henryzz I was more thinking about fairly deep sieving rather than what is effectively a wheel sieve. I have coded a crude sieve that can do things like sieve A=1 to 1M for x=-50k to 50k up to p=100k in about 2-3 hours.
More on this today. I'm going to releasing my code which can do this interval is a handful of seconds.

Last fiddled with by SethTro on 2020-11-04 at 12:04

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 6 2016-10-14 19:38 firejuggler Math 0 2016-07-11 23:09 Ricie Miscellaneous Math 24 2009-08-14 15:31 jasong Math 3 2005-05-15 04:01 clowns789 Miscellaneous Math 5 2004-01-08 17:09

All times are UTC. The time now is 11:49.

Sat Dec 5 11:49:44 UTC 2020 up 2 days, 8:01, 0 users, load averages: 2.96, 2.38, 1.94