mersenneforum.org probability a number is prime with a weighted k.
 Register FAQ Search Today's Posts Mark Forums Read

 2014-05-27, 14:28 #1 Trilo     "W. Byerly" Aug 2013 1423*2^2179023-1 5F16 Posts probability a number is prime with a weighted k. given a riesal prime (k*2^N-1 ), a nash weight of the k, and a range of n, calculate the expected number of primes in the range. I have done my research and it look like the average nash weight is 1751.542, so would am I correct in saying that this nash weight would be considered the same as the average prime number density? As an example, say the k value is 51 and the n range is 1M- 2M. The nash weight is 1550, divide it by 1751.542 and get ~0.885 times the average prime density. Then take the midpoint of the n ranges --> 1.5M (I know you will have to check each individual one, but for simplicities sake) and then plug this into the probability of finding a prime number formula: 0.885* (1/ln(51*2^1,500,000)) which comes out to .00000085 and then multiply this by 1000000 candidates to test to get .85, so we can say we will find an average of 0.85 primes in this range, or 85% chance of finding 1 prime right? Last fiddled with by Trilo on 2014-05-27 at 14:29
 2014-05-27, 15:29 #2 CRGreathouse     Aug 2006 22·1,483 Posts If the expected number of new primes is 0.85, this means the chance of a prime is about $1-e^{-.85}\approx57\%.$
2014-05-27, 20:15   #3
Trilo

"W. Byerly"
Aug 2013
1423*2^2179023-1

5×19 Posts

Quote:
 Originally Posted by CRGreathouse If the expected number of new primes is 0.85, this means the chance of a prime is about $1-e^{-.85}\approx57\%.$
Thanks, is everything else I did correct? I need to brush up on my statistics

2014-05-28, 05:59   #4
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

2×3×733 Posts

Quote:
 Originally Posted by Trilo Thanks, is everything else I did correct? I need to brush up on my statistics
Well, that k value had 3 primes between 250k and 500k, 3 between 500k and 1M, and 3 more between 1M and 2M. While 3 consecutive ranges could be mere luck, it appears your estimate is quite low for expected primes in the range.

The Nash weight is a measure of how many candidates survive a small sieve. To take sieving (and thus weight) into account, see:
http://www.mersenneforum.org/showpos...&postcount=157

-Curtis

2014-05-28, 13:58   #5
Trilo

"W. Byerly"
Aug 2013
1423*2^2179023-1

5×19 Posts

Quote:
 Originally Posted by VBCurtis Well, that k value had 3 primes between 250k and 500k, 3 between 500k and 1M, and 3 more between 1M and 2M. While 3 consecutive ranges could be mere luck, it appears your estimate is quite low for expected primes in the range. The Nash weight is a measure of how many candidates survive a small sieve. To take sieving (and thus weight) into account, see: http://www.mersenneforum.org/showpos...&postcount=157 -Curtis
Thanks for the post, I'll take a look at it. But looking more, it makes sense what you were saying about the amount of primes between the given ranges, as they double.

 2014-06-01, 22:55 #6 pepi37     Dec 2011 After milion nines:) 25048 Posts If you use formula from that thread you will get (1.781*ln(389651833000000000))/(3000000*ln(2)) = 0,0000346908898293 0,0000346908898293 is constant since all sieve we get from Primegrid is sieved on same depth ( I use sieve from 3M - 4M) So you just need to multiply number of candidates in sieve with 0,0000346908898293 and you will get expected number of primes in range 3M - 4M regardless of K. 25193 ( number of candidates in sieve of K 51) * 0,0000346908898293= 0.87 primes in range 3-4M for k= 31 it is 34986*0,0000346908898293= 1,21 primes in that range. So you need number with nash value around 2050 , and that number will have around 1 primes in that range. Last fiddled with by pepi37 on 2014-06-01 at 23:00 Reason: add more text
2014-06-02, 08:21   #7
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

2·3·733 Posts

Quote:
 Originally Posted by pepi37 If you use formula from that thread you will get (1.781*ln(389651833000000000))/(3000000*ln(2)) = 0,0000346908898293 0.87 primes in range 3-4M for k= 31 it is 34986*0,0000346908898293= 1,21 primes in that range. So you need number with nash value around 2050 , and that number will have around 1 primes in that range.
You used the chance of a prime at 3M to represent the entire range 3M to 4M. This is not accurate. If you use 3.5M, you'll be vaguely accurate; or an average of 3M and 4M, or any number of yet more accurate methods. At any rate, your 0.87 is optimistic by nearly 20%. I get something just under 0.75 for 51, and just over 1.0 for Steven's k=31.

2014-06-06, 15:55   #8
Trilo

"W. Byerly"
Aug 2013
1423*2^2179023-1

5·19 Posts

Quote:
 Originally Posted by VBCurtis Well, that k value had 3 primes between 250k and 500k, 3 between 500k and 1M, and 3 more between 1M and 2M. While 3 consecutive ranges could be mere luck, it appears your estimate is quite low for expected primes in the range. The Nash weight is a measure of how many candidates survive a small sieve. To take sieving (and thus weight) into account, see: http://www.mersenneforum.org/showpos...&postcount=157 -Curtis
How would you use this to find the chance of x primes in the range? Would it be something like 1- ((1- probability each candidate is prime)(1/x)* surviving candidates

so in other word, using the example in that post with 2 primes, 1- (1- 1/14997)(1/2)*18283= 45.6% chance to find 2 primes in that range

2014-06-06, 16:34   #9
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts

Quote:
 Originally Posted by Trilo How would you use this to find the chance of x primes in the range?
From http://en.wikipedia.org/wiki/Poisson_distribution, where the expected number of primes is 1.21, the probability of exactly k primes is:

1.21^k * e^(-1.21) / k!

For k=3:

1.21^3 * e^(-1.21) / 3! ~= 0.088

Note that for k=0, the formula simplifies to e^(-1.21), which should look familiar:
Quote:
 Originally Posted by CRGreathouse If the expected number of new primes is 0.85, this means the chance of a prime is about $1-e^{-.85}\approx57\%.$
You may also want to calculate the probability of >=3 primes, which should be (1 - (probability of 0) - (probability of 1) - (probability of 2))

Last fiddled with by Mini-Geek on 2014-06-06 at 16:36

2014-06-06, 17:45   #10
Trilo

"W. Byerly"
Aug 2013
1423*2^2179023-1

5×19 Posts

Quote:
 Originally Posted by Mini-Geek From http://en.wikipedia.org/wiki/Poisson_distribution, where the expected number of primes is 1.21, the probability of exactly k primes is: 1.21^k * e^(-1.21) / k! For k=3: 1.21^3 * e^(-1.21) / 3! ~= 0.088 Note that for k=0, the formula simplifies to e^(-1.21), which should look familiar: You may also want to calculate the probability of >=3 primes, which should be (1 - (probability of 0) - (probability of 1) - (probability of 2))
Thank you. I am planning on making some sort of probability calculator so I can know a few things about finding primes in ranges.

2014-06-06, 18:21   #11
Trilo

"W. Byerly"
Aug 2013
1423*2^2179023-1

5·19 Posts

Quote:
 Originally Posted by Mini-Geek From http://en.wikipedia.org/wiki/Poisson_distribution, where the expected number of primes is 1.21, the probability of exactly k primes is: 1.21^k * e^(-1.21) / k! For k=3: 1.21^3 * e^(-1.21) / 3! ~= 0.088 Note that for k=0, the formula simplifies to e^(-1.21), which should look familiar: You may also want to calculate the probability of >=3 primes, which should be (1 - (probability of 0) - (probability of 1) - (probability of 2))
I am now getting conflicting results. Using the formula you gave me,

with expected number at = 0.076
and k= 1:

(.076^1)*(e^-.076)/1

comes out at 7.04% but

1-.e^-.076

comes out to 7.31%

Last fiddled with by Trilo on 2014-06-06 at 18:23

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 6 2017-01-30 02:54 carpetpool Miscellaneous Math 27 2017-01-19 21:00 Unregistered Information & Answers 2 2010-05-25 20:51 vimil Information & Answers 13 2007-12-12 11:21 Deamiter Software 4 2002-10-11 16:36

All times are UTC. The time now is 04:01.

Wed Oct 28 04:01:31 UTC 2020 up 48 days, 1:12, 2 users, load averages: 2.36, 1.92, 1.81