## Other

drummers-lowrise

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

Author Message
Message 148740 - Posted: 16 Feb 2021 | 16:25:40 UTC

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.8e-8 in 1. Thus we are supposed to find 2.8e-8 * 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 Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 671
ID: 164101
Credit: 305,042,960
RAC: 0 Message 148741 - Posted: 16 Feb 2021 | 16:34:14 UTC - in response to Message 148740.

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 Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 671
ID: 164101
Credit: 305,042,960
RAC: 0 Message 148742 - Posted: 16 Feb 2021 | 16:49:43 UTC

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

Message 148900 - Posted: 20 Feb 2021 | 10:22:15 UTC - in response to Message 148741.

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 Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 671
ID: 164101
Credit: 305,042,960
RAC: 0 Message 148913 - Posted: 20 Feb 2021 | 13:23:31 UTC - in response to Message 148900.

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.

Message 149513 - Posted: 17 Mar 2021 | 19:55:17 UTC

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

Message 149520 - Posted: 17 Mar 2021 | 21:27:26 UTC - in response to Message 149513.

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

Message 149522 - Posted: 17 Mar 2021 | 21:35:18 UTC - in response to Message 149513.

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 table--also linked by JeppeSN--that li(x) is a better estimate than x/ln(x).)

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).