PrimeGrid
Please visit donation page to help the project cover running costs for this month

Advanced search

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

Author Message
Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 411
ID: 1241833
Credit: 188,490,185
RAC: 997,696
321 LLR Amethyst: Earned 1,000,000 credits (1,058,073)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Amethyst: Earned 1,000,000 credits (1,165,078)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,148,593)PPS LLR Amethyst: Earned 1,000,000 credits (1,225,852)PSP LLR Amethyst: Earned 1,000,000 credits (1,248,861)SoB LLR Amethyst: Earned 1,000,000 credits (1,669,219)SR5 LLR Amethyst: Earned 1,000,000 credits (1,060,324)SGS LLR Amethyst: Earned 1,000,000 credits (1,152,304)TRP LLR Amethyst: Earned 1,000,000 credits (1,039,866)Woodall LLR Amethyst: Earned 1,000,000 credits (1,129,385)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)WW Double Bronze: Earned 100,000,000 credits (161,640,000)GFN Turquoise: Earned 5,000,000 credits (7,149,778)PSA Amethyst: Earned 1,000,000 credits (1,022,470)
Message 148740 - Posted: 16 Feb 2021 | 16:25:40 UTC
Last modified: 16 Feb 2021 | 16:30:51 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?
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^8-1979 & 1281979 + 4 (cousin prime)

Yves Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 669
ID: 164101
Credit: 305,042,960
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (305,042,960)
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
Send message
Joined: 19 Aug 12
Posts: 669
ID: 164101
Credit: 305,042,960
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (305,042,960)
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.

Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 411
ID: 1241833
Credit: 188,490,185
RAC: 997,696
321 LLR Amethyst: Earned 1,000,000 credits (1,058,073)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Amethyst: Earned 1,000,000 credits (1,165,078)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,148,593)PPS LLR Amethyst: Earned 1,000,000 credits (1,225,852)PSP LLR Amethyst: Earned 1,000,000 credits (1,248,861)SoB LLR Amethyst: Earned 1,000,000 credits (1,669,219)SR5 LLR Amethyst: Earned 1,000,000 credits (1,060,324)SGS LLR Amethyst: Earned 1,000,000 credits (1,152,304)TRP LLR Amethyst: Earned 1,000,000 credits (1,039,866)Woodall LLR Amethyst: Earned 1,000,000 credits (1,129,385)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)WW Double Bronze: Earned 100,000,000 credits (161,640,000)GFN Turquoise: Earned 5,000,000 credits (7,149,778)PSA Amethyst: Earned 1,000,000 credits (1,022,470)
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.
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^8-1979 & 1281979 + 4 (cousin prime)

Yves Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 669
ID: 164101
Credit: 305,042,960
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (305,042,960)
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.

Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 411
ID: 1241833
Credit: 188,490,185
RAC: 997,696
321 LLR Amethyst: Earned 1,000,000 credits (1,058,073)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Amethyst: Earned 1,000,000 credits (1,165,078)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,148,593)PPS LLR Amethyst: Earned 1,000,000 credits (1,225,852)PSP LLR Amethyst: Earned 1,000,000 credits (1,248,861)SoB LLR Amethyst: Earned 1,000,000 credits (1,669,219)SR5 LLR Amethyst: Earned 1,000,000 credits (1,060,324)SGS LLR Amethyst: Earned 1,000,000 credits (1,152,304)TRP LLR Amethyst: Earned 1,000,000 credits (1,039,866)Woodall LLR Amethyst: Earned 1,000,000 credits (1,129,385)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)WW Double Bronze: Earned 100,000,000 credits (161,640,000)GFN Turquoise: Earned 5,000,000 credits (7,149,778)PSA Amethyst: Earned 1,000,000 credits (1,022,470)
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?
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^8-1979 & 1281979 + 4 (cousin prime)

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1503
ID: 306875
Credit: 34,128,060
RAC: 8,206
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Jade: Earned 10,000,000 credits (12,265,024)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)WW Turquoise: Earned 5,000,000 credits (9,640,000)GFN Amethyst: Earned 1,000,000 credits (1,707,013)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 149520 - Posted: 17 Mar 2021 | 21:27:26 UTC - in response to Message 149513.
Last modified: 17 Mar 2021 | 21:51:24 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?


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 Fernando
Project administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 162
ID: 1108183
Credit: 9,556,308
RAC: 5,650
321 LLR Gold: Earned 500,000 credits (575,511)Cullen LLR Bronze: Earned 10,000 credits (82,217)ESP LLR Bronze: Earned 10,000 credits (16,570)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (12,551)PPS LLR Ruby: Earned 2,000,000 credits (2,797,959)PSP LLR Bronze: Earned 10,000 credits (26,371)SoB LLR Silver: Earned 100,000 credits (258,849)SR5 LLR Bronze: Earned 10,000 credits (59,499)SGS LLR Silver: Earned 100,000 credits (148,878)TRP LLR Silver: Earned 100,000 credits (195,905)Woodall LLR Bronze: Earned 10,000 credits (40,424)321 Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,001,667)AP 26/27 Bronze: Earned 10,000 credits (72,774)WW Bronze: Earned 10,000 credits (12,000)GFN Silver: Earned 100,000 credits (248,769)
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).)

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

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2021 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 6.18, 5.99, 5.66
Generated 14 Jun 2021 | 15:53:59 UTC