Merten's Theorem is that the product of (1-1/p) for all primes less than x is asymptotically exp(-gamma)/ln(x). This is useful for estimating the effectiveness of trial factoring because the product is the fraction of numbers left after removing primes less than x. This is potentially useful in our resource model for what I have been thinking of as two distinct issues – the number of candidates presently in the system and the rate at which sieving will remove these candidates.
We will need to modify Merten’s theorem by Proth Weights. We need Proth Weights because our sequences have divisibility properties that differ from the divisibility of sequential integers in standard ways. For example, in sequential integers, ½ are divisible by 2, then 1/3 of the remainder are divisible by 3, then 1/5 of the remainder are divisible by 5. For our remaining k values, none of the numbers we are testing for prime are divisible by 2, ½ are divisible by 3, ½ of the remainder are divisible by 5. It gets even stranger with 7 – for most of our k values 1/3 of the remainder are divisible by 7, but for two of the k values, none of the remainder are divisible by 7. I explored these divisibility properties by constructing partial coverings in the prediction thread, but better estimates of the Proth Weight are contained in Table 5 of Yves Gallot’s paper on weights.
We might apply Merten’s Theorem in absolute terms or in relative terms. It’s most elegant in relative terms. If we previously sieved up through p=S, the number of values left from a range of size N will be N*a / ln(S), where is a constant calculated as the product of the Proth Weight and exp(-gamma). If we now extend the sieve through p=T, there will now be N*a / ln(T) left. The reduction factor is ln(S)/ln(T). This has some simple consequences. For example, the main sieve is now around 15T. This predicts that if we extend that sieve to 200T, the number of candidates will reduce by a factor of ln(15T)/ln(200T) = 0.92 – about 8% of the remaining candidates will be removed. It also predicts that removing half the candidates requires squaring the sieve limit.
This sounds good, but does it work? Let’s see how well it predicts the current status. We can check the status of sieving in the Sieve Coordination Thread. When I checked, the sieving was nearly complete through 15.35T, there was a completed block from 17.42T-18.14T, and some scattered ranges even higher. The effect of the higher block should be ln(17.42T)/ln(18.14T)=0.9987, so we can ignore that. Using Yves Gallot’s Proth Weights, the average weight for the twelve remaining k values is 0.163. The value 0.163 * exp(-gamma) / ln(15.35T) = 0.00302. In each range of 1 million n’s, from the 12 million original candidates, this method predicts that on average there will be 36,245 remaining candidates. Looking at MikeH's Sieve Statistics for the main sieve (n=3M to 20M), we see that this estimate is about 1% high:
These average 35909. If we lower the Proth Weight estimate to 0.1618 we match very closely. Yves Gallot only reported the Proth Weights to 2 digits, so an adjustment of this magnitude seems reasonable.
Merten’s theorem with the adjusted average proth weight seems well suited for calculating the present number of candidates. The remaining question is how well it describes the incremental process of sieving. Fortunately Nuri has excellent data on how that process has been going:
Originally posted by Nuri Wblipp, could you please also check the 40000 = y * (x^1.06) formula I am using in Sieve: Distribution of Factors vd. p value thread against Merten's theorem? The formula is for the 3m-20m sieve. y = # factors per G and x = p level in terms of G.
Between m=3M and n=17M for twelve k-values, there are 12*17*10^6 n values before sieving. Merten’s Theorem predicts that after sieving to “p” in G, the number of candidates left will be 12*17*10^6 * 0.1618 * exp(-gamma) / ln(p*10^9). The difference between this value at “p” and at “p+1” represent the numbers sieved away, and every one of the sievings represents a factor. The following is a plot of the number of factors found using Nuri’s function and using the Merten prediction. Blue is Nuri and red is Merton The agreement is excellent. I’m convinced we can use Merten’s Theorem to model the sieving.
Reply With Quote