Sieving is a very misunderstood subject. Eventually I intend to expand on the below, which explains some of the principles involved. This is V0.0 presently!
Basically, the maths says that the density of primes in a large set of related numbers is dependent on which small primes can be divisors of members of that set. In particular, most of the time each prime p contributes a thinning of the prime density in the set by a (p-c)/p factor for each prime which can be a divisor, and c is the number of residues mod p that will generate p as a factor. If p cannot be a divisor of any member in the set, then the factor still holds, it's just that c=0.
The final density is the product of all these factors.
Ordinary ranges of numbers and arithmetic progressions, which include sets such as fixed-n Proth-form families, have _every_ prime in this product, and c=1 for every prime.
Numbers like the above (arithmetic progressions) with a primorial scale factor only have primes greater than the prime in the primorial in their product. Again c=1 for those primes, and c=0 for the primes in the primorial component. e.g., numbers of the form:
Arbitrary sets of numbers that have been presieved to P no longer have primes <=P in their density product; i.e. the product only consists of products of the form (p-1)/p for p>P. All these terms are very close to 1.
GFN numbers can only have a restricted set of primes in their product, p=k.2^n+1, and each such prime removes 2^n candidates.
This means that an unsieved set of GFN numbers can have a wildly deviant density from that of arbitrary numbers. Most of that deviance is caused by the lack of primes of the form k.2^n+1 with _small_ k.
However, sieving GFN numbers is the great leveller, as _no_ sieved GFN number can have factors that are k.2^n+1 with small k, assuming you've sieved beyond k.2^n+1. That means that the density product consists of terms that are again all rather close to 1.
Now while these terms for sieved arbitrary numbers and sieved GFN numbers are different, on average they work out to having a very similar value. Once the massive effects of the small primes has been negated by sieving, there's very little left to choose between any particular form density-wise.
Therefore, for working out the expected density of primes in the candidates that remain after a sieve, the single most important issue is simple how deep you sieved (and their size, obviously), and not what set of numbers you were looking at originally. The number of candidates that _remain_ in the set after the sieving can vary massively, and therefore the prime number yield for similarly-sized sets can also vary dramatically. Don't confuse the concepts.
Last modified: 2003/07/23
Another hastily constructed page by Phil Carmody
Home /
Maths /
Trivia /
index.html