mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2014-05-27, 14:28   #1
Trilo
 
Trilo's Avatar
 
"W. Byerly"
Aug 2013
1423*2^2179023-1

5F16 Posts
Default 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
Trilo is offline   Reply With Quote
Old 2014-05-27, 15:29   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22·1,483 Posts
Default

If the expected number of new primes is 0.85, this means the chance of a prime is about 1-e^{-.85}\approx57\%.
CRGreathouse is offline   Reply With Quote
Old 2014-05-27, 20:15   #3
Trilo
 
Trilo's Avatar
 
"W. Byerly"
Aug 2013
1423*2^2179023-1

5×19 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
Trilo is offline   Reply With Quote
Old 2014-05-28, 05:59   #4
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2×3×733 Posts
Default

Quote:
Originally Posted by Trilo View Post
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
VBCurtis is online now   Reply With Quote
Old 2014-05-28, 13:58   #5
Trilo
 
Trilo's Avatar
 
"W. Byerly"
Aug 2013
1423*2^2179023-1

5×19 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.
Trilo is offline   Reply With Quote
Old 2014-06-01, 22:55   #6
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

25048 Posts
Default

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
pepi37 is offline   Reply With Quote
Old 2014-06-02, 08:21   #7
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·3·733 Posts
Default

Quote:
Originally Posted by pepi37 View Post
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.
VBCurtis is online now   Reply With Quote
Old 2014-06-06, 15:55   #8
Trilo
 
Trilo's Avatar
 
"W. Byerly"
Aug 2013
1423*2^2179023-1

5·19 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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
Trilo is offline   Reply With Quote
Old 2014-06-06, 16:34   #9
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by Trilo View Post
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 View Post
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
Mini-Geek is offline   Reply With Quote
Old 2014-06-06, 17:45   #10
Trilo
 
Trilo's Avatar
 
"W. Byerly"
Aug 2013
1423*2^2179023-1

5×19 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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.
Trilo is offline   Reply With Quote
Old 2014-06-06, 18:21   #11
Trilo
 
Trilo's Avatar
 
"W. Byerly"
Aug 2013
1423*2^2179023-1

5·19 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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
Trilo is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Probability that n is a prime power carpetpool Miscellaneous Math 6 2017-01-30 02:54
Probability that n is a semi-prime or prime carpetpool Miscellaneous Math 27 2017-01-19 21:00
Sieve depth vs. prime probability Unregistered Information & Answers 2 2010-05-25 20:51
Probability of a Mersenne number being prime vimil Information & Answers 13 2007-12-12 11:21
Probability of finding a prime number 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.