Choose sub-page

The Maths

Prime Number Theory says that the chance of a random integer x being prime is about 1/log x

For x = k*b^n+/-1, chance is about w/log (k*b^n-1)
To find the probability for a fixed k over a given range we integrate from n = A to n = B.
Integrating w/log (k*b^n-1) gives:

#Primes = w * (ln(ln k + B*ln b) - ln(ln k + A*ln b))/ln b


ln(x) is the natural logarithm ln(x), i.e. log to the base e.

Weight is scaled so w=1.0 has the same density of primes as a randomly chosen set of odd numbers of the same magnitude.

w = k*b*P1e6 / (li(110,000*k*b)-li(100,001*k*b))


P1e6 is the number of candidates remaining after testing the range n=100001 to 110000 for factors up to 1 million.

> srsieve -n 100001 -N 110000 -P 1e6 "k*b^n+/-1"

It is similar to the Nash weight but sieved to a deeper depth to be more accurate and not skewed toward small factors.

li(X) is the logarithmic integral.

li(x) ∼ x/ln(x) + x/ln(x)² + 2x/ln(x)³ + 6x/ln(x)⁴ + 24x/ln(x)⁵ + ...





Last update: Sun 25 Jan 2014 7:05 WST

Based on pages compiled and maintained by Gary Barnes