Proth and Riesel Primes
TheCount's probability page.
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