Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
General discussion :
Number of primes below a certain value when not testing all numbers
Author 
Message 
BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 430 ID: 1241833 Credit: 235,123,868 RAC: 960,743

I wanted to estimate how many primes can be expected when testing all number of the form k * 2^n + 1 up to a certain n.
The simplify the matter I only took the prime number theorem into account. Since k is small compared to 2^n I think it can be said that:
Pi(k * 2^n + 1) ~ 2^n/ln(2^n)
This is the same as 2^n/n * log(e)/log(2) = 2^n/n * 1.443. So for n = 30 we expect 51.6 million primes (according to PrimePage it's 54.4 million  close enough).
Sounds great for finding Proth primes, but we only test n numbers, not 2^n. To accomodate for that we can estimate the fraction of numbers we check to be n/2^n. Or in our example we check 30 numbers out of 2^30, or 2.8e8 in 1. Thus we are supposed to find 2.8e8 * 51.6e6 or around 1.46 primes. So far so good, but generalized:
n/2^n * 2^n/n * 1.443
which is a constant value of 1.443.
I doubt that's true because it would mean no matter which n you choose you always end up with expected number of primes of 1.443.
You could argue that with increasing n the fraction of tested numbers decreases since the range grows exponentially and the amount of tested numbers only grows linearly with n and combined with the growing number of primes it might even out to a constant 1.443 but obviously that's not the case  or ist it?
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 4,400,000  

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 671 ID: 164101 Credit: 305,042,960 RAC: 0

The simplify the matter I only took the prime number theorem into account. Since k is small compared to 2^n I think it can be said that:
Pi(k * 2^n + 1) ~ 2^n/ln(2^n)
This is the number of primes (all of them) up to k * 2^n + 1, not the number of primes of the form k * 2^n + 1 with k < K up to K * 2^N + 1.
 

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 671 ID: 164101 Credit: 305,042,960 RAC: 0

There are 169,369 primes of the form k * 2^n + 1 for k < 10,000 and n <= 1,550,000.  

BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 430 ID: 1241833 Credit: 235,123,868 RAC: 960,743

That's what I was trying to do: 2^n/ln(2^n) is approximately the number of primes up to k*2^n+1.
But how do I proceed if I want to limit it to those of the Proth form? I think I need to multiply the value by n/2^n since we only check n numbers out of k*2^n+1. But then I end up with the constant value 1.44...
How did you come up with the 169,369? I'm missing something, but have no idea what.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 4,400,000  

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 671 ID: 164101 Credit: 305,042,960 RAC: 0

But how do I proceed if I want to limit it to those of the Proth form? I think I need to multiply the value by n/2^n since we only check n numbers out of k*2^n+1. But then I end up with the constant value 1.44...
The probability that x is prime is P(x) ~ 1 / log(x) and if x is odd, P(x) ~ 2 / log(x).
x = k*2^n + 1 is odd.
The numbers of primes for 1 <= k <= K, k odd and 1 <= n <= N is about
sum_{1 <= k <= K, k odd} sum_{1 <= n <= N} 2 / log(k*2^n + 1)
~= sum_{1 <= k <= K, k odd} sum_{1 <= n <= N} 2 / (n * log(2) + log(k)).
If K = 10,000 and N = 1,550,000, the expected number of primes is 169503.
How did you come up with the 169,369? I'm missing something, but have no idea what.
This is the actual number of primes in the range. The range was completly tested.
 

BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 430 ID: 1241833 Credit: 235,123,868 RAC: 960,743

I thought about this for a while now and I don't really understand why it's often stated that the probability when picking a random number x that it is prime is 1/ln(x).
I know that there are approximately x/ln(x) primes smaller than x. And thus to find the fraction of primes we can take the fraction (x/ln(x))/x = 1/ln(x).
But that is the probability for a random number r with 0 < r < x to be prime. Not for r ~ x. It would be true if the primes were homogeneously distributed. But the prime density decreases with increasing size of the numbers.
So my question is, what is the probability if we don't use the range 0 < r < x but 0.9x < r < x for r to be prime?
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 4,400,000  


I thought about this for a while now and I don't really understand why it's often stated that the probability when picking a random number x that it is prime is 1/ln(x).
I know that there are approximately x/ln(x) primes smaller than x. And thus to find the fraction of primes we can take the fraction (x/ln(x))/x = 1/ln(x).
But that is the probability for a random number r with 0 < r < x to be prime. Not for r ~ x. It would be true if the primes were homogeneously distributed. But the prime density decreases with increasing size of the numbers.
So my question is, what is the probability if we don't use the range 0 < r < x but 0.9x < r < x for r to be prime?
Believe us, believe us, 1/(ln x) is a good "probability" that x is prime!
I can answer your 0.9x question with an example. Set x=10^9 in the following. Then the number of primes less than x is 50'847'534. So as a "probability" we have 0.0508... (a bit over 5%). If you compare with x/(ln x), that is about 48'254'942. You see the agreement is not so fantastic.
Now you want the number of primes between 0.9x and x, so between 9*10^8 and 10^9. There are 4'838'319 primes in this interval. So that is a probability of 0.0483... (a bit under 5%). For comparison 1/(ln x) is 0.0482549... So you see a much better approximation than with the comparison between x/(ln x) and number of primes under x.
You could also take the midpoint in the interval, so 1/(ln (9.5*10^8)) = 0.0483746...
End of the 10^9 example.
Do not think that x/(ln x) is a fantastic estimate for the number of primes under x. It is good enough so that when x tends to infinity, the relative error tends to zero. But this is true for many functions, for example x/(666666666666 + ln x) also has this property. There are many function that have this property. Is x/(ln x) the best of them in some sense? Nope!
A better estimate for the number of primes less than x comes from adding all the 1/(ln r) for r from 2 up to x, that is 1/(ln 2) + 1/(ln 3) + 1/(ln 4) + 1/(ln 5) + ... + 1/(ln r). If you know a lot of calculus, you can see that this sum is very related to an integral, from 2 to x, of (1/(ln r)) dr. That expression is called Li(x). Li(x) is better at predicting the number of primes under x than is your x/(ln x).
I suggest you look carefully at the table Table of π(x), x / log x, and li(x) and think about it.
/JeppeSN  

Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 165 ID: 1108183 Credit: 9,883,087 RAC: 8,152

This post repeats much of what JeppeSN said, but maybe it'll be useful anyway.
A better heuristic: the number of primes between A and B is approximately the integral of 1/ln(x) from A to B. This is essentially equivalent to saying that the probability when picking a random number x that it is prime is 1/ln(x). For intervals [1,x], it's much more accurate than saying there are approximately x/ln(x) primes smaller than x. (See logarithmic integral. You can see in this tablealso linked by JeppeSNthat li(x) is a better estimate than x/ln(x).)
So a good answer to what is the probability if we don't use the range 0 < r < x but 0.9x < r < x for r to be prime? would be (li(x)  li(0.9x))/(x  0.9x).
Finally, regarding your point: But that is the probability for a random number r with 0 < r < x to be prime. Not for r ~ x. It would be true if the primes were homogeneously distributed. But the prime density decreases with increasing size of the numbers.
This is precisely why x/ln(x) isn't a great estimate: it undercounts primes that are much smaller than x. The logarithmic integral corrects this error. However, if x is large enough, the percentage error will go to zero. Think of it this way: if ln(x) = 1000, then a majority of numbers r in [0,x] will satisfy 999 < ln(r) < 1000. So for most values of r, 1/ln(r) will be between 1/1000 and 1/999. It's not a big difference.  

Post to thread
Message boards :
General discussion :
Number of primes below a certain value when not testing all numbers 