Printable View
kinda a random question but how do our odds of finding a pime at a certain N value compare to GIMPS? At equal N values are we more likely to find a prime on a particular test or are they (or are they the same?). I doubt they are the same because of different probabilities or different types of primes and different sieve/ factoring depths. I've noticed that per K we have mny fewer values then they have to test though. Just looking for some info from some of the math experts around here.
I'm no expert, but I guess it has something to do with the proth weight.
BTW, as far as I know their chances are higher.
I'm no expert either but I'm pretty sure that the probablility of any one of our k/n's being prime is the same as a gimp's k/n (gimps has k=2) being prime for the same size n.
example:
probablility gimps n=X being prime = probablility Sob n=X being prime fpr the same X
Where the difference comes in is when we start talking about prime denisity in a particular range of n.
Example GIMPS may find 2 primes between n=X and n=Y, but SOB may find 4 primes between n=X and n=Y. But this is only because there are twice as many tests between X and Y with SOB compared to GIMPS. (I think I have this the wrong way around but the points are still valid).
also, SOB wants just the first prime for the k's. GIMPS are looking for as many as they can find for k=1. The way the first primes are distributed for different k might be very different from how primes are distributed for a particular k. Hence, i will be surprised if there is any correlation.
jaat
From that point of view, GIMPS has ~55,000 tests per million n range after sieving to 2^60 min, whereas we have ~26,500 tests per million n range for remaining 10 k after sieving to 2^49 min.
And ~26,500 figure will continue to drop futher, mainly as we find more primes but also some more from sieving (~2%=550 per million n range for each 2^1 increment) and factoring (~1%=265 per million n range).
That's interesting nuri where did you get the 550 per million n range per 2^1. Is it another probablity/equation and I'm sure it depends on k-weight.Quote:
Originally posted by Nuri
And ~26,500 figure will continue to drop futher, mainly as we find more primes but also some more from sieving (~2%=550 per million n range for each 2^1 increment) and factoring (~1%=265 per million n range).
I was refering to per single K value as it is understood that there are different proth wieghts. If we were to find 9 primes in the nextyear and end up with one K value remaining would we have a better chance offinding a prime per test than would GIMPS. We would of course catch up to them in a matter of weeks if that N value was 67607 but what would be the probability of finding a prime compared to GIMPS once we reached the same level as them.
Nope. It's just a rough estimate based on Mike's stats (see the project page ). I calculated it as: 11000/20. As you may see, thats's a very rough estimate.Quote:
Originally posted by vjs
That's interesting nuri where did you get the 550 per million n range per 2^1. Is it another probablity/equation and I'm sure it depends on k-weight.
In fact, most of the 2^48-2^49 range was sieved with 1m-20m dat, if not by the moving lower end one as we use currently. So, speaking of 2^48 to 2^49 range, I guess one might assume the sieve in that p range was conducted with an average dat file size of 18.9 or so. Thus, 11035/18.9 = 584 factors per million n range.
But, the actual per million n range figure will probably be lower as we progress. See table below.
2^40 to 2^41 18387 Decrease in # factors
2^41 to 2^42 17306 (5.88%)
2^42 to 2^43 15896 (8.15%)
2^43 to 2^44 15352 (3.42%)
2^44 to 2^45 14509 (5.49%)
2^45 to 2^46 13890 (4.27%)
2^46 to 2^47 13779 (0.80%)
2^47 to 2^48 11750 (14.73%)
2^48 to 2^49 11035 (6.09%)
The decrease averages at 6.18% per ^1 increment. Thus, a more precise estimate would be to incorporate that drop as well.
If no new primes are found, the table would probably look like as below when finished (or even less, due to the effect of moving lower bound i.e. double check boundary).
2^49 to 2^50 10353 => 548 per million n range
2^50 to 2^51 9713 => 514 per million n range
2^51 to 2^52 9112 => 482 per million n range
The figures above still lacks the effect of moving lower boundary effect. But per million figures will not change much, although total number of factors found will decrease to a degree based on relative speeds of double check PRP vs. sieve.
Of course, the decrease in number of factors found by factoring will decrease as well, as sieve progresses.
1% is again a rough estimate based on 49,1.5 setting at P-1, and assumes all of the k/n pairs are tested.
So, as sieve progresses, i.e. we start to use 50 instead of 49 at P-1 etc., it will also decrease.
Not to mention that not all of the k/n pairs are tested for P-1.
Keroberts,
The answer is yes we have a better chance and no the chances are equal.
First on a per test basis we have the exact same chance of finding a prime as any other project. The probablility of primailtiy is equal to something like.
probability = 1 / ln n where m is a base 2
So this means on a per test basis as n increases (or the shear size of the number increases) the chances of n being prime decreases. But the form of the equation doesn't matter much.
k*2^n-1, k*2^n+1, 2^n-1, 2^n+1, (x+y+z-h+42)*2^n-17, doesn't matter... its just the size of the number the equation produces. And the probability equation generally holds for base 2.
What this means is currently on a per tests basis we have a better chance of finding primes than gimps b/c our numbers are smaller. Now once we get to n=24M our chances will be the exact same. But when considering higher n and chances of finding primes you must take into account sieving and factoring. IF an n is seive very deep and factored as best as possible, if no factor is produced of course the chances of being prime goes up.
Take SoB for example. We started out with somethine like 40k k/n pairs per 1M now we are around 26K per 1M, b/c alot of k/n's have been eliminated through sieve and factoring. In this respect our chances of a k/n being prime has increased by 40/26 (this is starting to get a little to detailed).
Now currently if you wanted to randomly test one n=24M number a gimps would be a better choice. Why b/c they have sieved their numbers to p=2^60 and we have sieve those numbers above 20M to only p=2^43, also gimps factors their numbers pretty deep before testing we havn't do any factoring on those numbers. So currently if you wanted to test one number at n=24M gimps would be a better choice.
This is the main reason why people push for deep sieve depths and want to intergrate factoring into the main client.
Is this a good answer or do you have more questions???
i thoguht the prime chances with the 1 / ln n where m is a base 2
was just the probability of a prime in a certain range? not sur though. per N value even though they have sieved deeper we have fewer values per million per K. this would mean that if there is a certain probability of finding a prime for K = 67607 between 25 million and 26 million we would have fewer tests and a better chance per test of finding a prime. (if our sieve was at the level it currently is for that depth.) does this make sense?
"i thoguht the prime chances with the 1 / ln n where m is a base 2
was just the probability of a prime in a certain range? not sur though. "
I'm almost 100% postive that the probabilty of any n being prime is 1 / ln n on a per test bases, this is without any sieving factoring or ???.
But like you said we increase our probablility of finding a prime within a range of n at this n-level by sieving and factoring...
"per N value even though they have sieved deeper we have fewer values per million per K. this would mean that if there is a certain probability of finding a prime for K = 67607 between 25 million and 26 million we would have fewer tests and a better chance per test of finding a prime. (if our sieve was at the level it currently is for that depth.) does this make sense?"
Yes this makes total sence and my "k*2^n-1, k*2^n+1, 2^n-1, 2^n+1, (x+y+z-h+42)*2^n-17, doesn't matter" isn't totally correct if your considering a range b/c those equations are a form of sieving/factoring in itself. However if you consider there are X primes between n=30M and n=40M not all of those primes fit the equations of gimps or sob. So even if a prime exists in this range it may not help us.
Does this make sence???
You know of course that both gimps and sob has missed or more correctly not looked for all primes below the current n value. If you wanted to find all primes you'd need to test every number 1,2,3,4,5,6,...
Perhaps, I'm totally missing what your getting at or I'm wrong, could someone else comment?
i think we'r on the same page but i blieve that SOB has proven for all of our K values that thre are no rpimes aound 1,2,3,4 because we have factors for almost all N values below 1000. and the few we haven't have been prped many times.
Proth weights from link are computed by testing n=1-10000 and then scaled by 1/1751.542 so 1.0 is the same density of primes as a randomly chosen set of odd numbers of the same magnitude.
Mersenne numbers have a k=1, but in order to achieve that final -1 instead of a +1, you're supposed to use a negative k, i.e. k=-1.
k : -1, w : 0.6714083932900268
k : 67607, w : 0.03539738127889597
k : 22699, w : 0.040535710819380864
k : 19249, w : 0.043390338341872475
k : 27653, w : 0.06394365650381208
k : 33661, w : 0.09591548475571811
k : 21181, w : 0.09648641026021643
k : 24737, w : 0.0981991867737114
k : 4847, w : 0.09877011227820973
k : 10223, w : 0.118752504935651
k : 55459, w : 0.14101859961108557
This applet places Mersenne numbers as being much more likely to be prime. In fact, that is what we have observed to date. GIMPS has found 38 primes for n < 8,000,000. If you stipulate Mersenne's n value to be greater than the largest of SoB's k values, you get 11 primes from 55,459 < n < 8,000,000. Whereas, for these Sierpinsky number candidates, we have found zero primes.
I am not qualified enough to say, on a candidate by candidate basis, that the odds of being prime are not the same. But over a longer haul, it looks like a good bet that given some range of n, GIMPS is more likely to be prime.
Happy hunting!
One thing to consider, though, is the fact that the more likely a k is prime, the earlier it isn't considered anymore for SoB.
I thing some of the eliminated k's had higher proth weights -but not as high as Mersenne numbers have, of course.