probability that a test turns out prime?

[eatmadustch]

Hi
Does anyone (probably with more knowledge in number theory than me ;)) know what the probability is that a test is prime? I guess this is a function of the current n, isn't it? Also: what is the possibility that the test reports "probable prime", but it actually just turns out not to be prime?

Thanks
Ben

P.S. I know you could work out a rough estimate by dividing 5 by the amount of tests we've done. But that won't be very exact!

[wblipp]

Originally posted by eatmadustch
Hi
Does anyone (probably with more knowledge in number theory than me ;)) know what the probability is that a test is prime? I guess this is a function of the current n, isn't it?

We are handing out tests around 3.7 million. Our average k value is about 27000, so the average value is about x=27000*2^3700000. If we were testing every number in this size range, we would expect to find primes about 1/ln(x) - about one every 2.6 million.

But these are Proth numbers with low Proth Weight. Our average proth weight is about .163. If we were testing all Proth numbers, the probability of finding a prime would be .163/ln(x), about once every 16 million tests.

But the Sieving is mostly completed through 23x10^12. Merten's Theorem tells us the fraction of remaining numbers should be exp(-gamma)/ln(23*10^12) = 0.018. [EDIT - see below - this number also needs a Proth Weight Adjustment, resulting in 1 in 340]] So the chance that one of the trials we really conduct will find a prime is about one in [EDIT - 47,000 (was incorrectly reported as 290,000 before fixing the Proth Weights on Merten's Theorem)].

[smh]

Okay, i don't know much about math at all, but....

..I think you shouldn't count the weight of the number because thats already reflected in the sieving. Numbers with a lower weight have more candidates removed by sieving already.

:confused:

[MikeH]

So the chance that one of the trials we really conduct will find a prime is about one in 290,000. 290,000 feels a bit high. There are currently less than 36000 candidates per million n. So that means you are very certain that a prime will be found within the next 8M n. Which means 50% probability of finding next prime before n=7.5M. We also have to consider the other 11 k. Each of those contribute (although to a lesser degree) to improve the probability.

Even the most pessimistic calculations suggest finding the next prime before n=6.5M. This would give us something better than one in 108,000.

[eatmadustch]

I've done 310 tests. Does that mean that the chance I should have found at least one prime is like (1-(107999/108000)^310) = 0.29%! seems rather high to me!

[MikeH]

(1-(107999/108000)^310) = 0.29%! seems rather high to me! ... or more simply (310*100)/108000 = 0.29%. Correct, if you do the math in reverse, 100/0.29 = 345, so 345 users with the same tally as yourself would have completed 345*310=106950 tests, i.e. 100% probability.

Remember however, the probability will change for any given point in time, however assuming some of these 310 tests were performed before the first five primes were found, their associated probabilities will have been higher, thus your cumulative probability will be greater than 0.29%.

[eatmadustch]

Originally posted by MikeH
... or more simply (310*100)/108000 = 0.29%. Correct, if you do the math in reverse, 100/0.29 = 345, so 345 users with the same tally as yourself would have completed 345*310=106950 tests, i.e. 100% probability.


Nope! You will never get 100% probability. With so many users you could expect a prime, but in fact it's only (1-(107999/108000)^(345*310)) = 62.9%. You were very close (but not exact) with (310*100)/108000 = 0.29%, but that is only because 310 is very small compared to the 108000. When the 310 grow to 106950 you can't do this approximation anymore.

this is of corse assuming that you are allowed to calculate this binomially!

[MikeH]

Nope! You will never get 100% probability. Er...no. There are hopefully 12 more primes to find, thus if we were able to look to the future to the point where that 12th prime is found, the cumulative probability between now and then would be 1200%, thus greater than 100%.

But this can only be a prediction, so I'm not going to split hairs. I'm simply making the point that one in 290,000 feels too high, and that 0.29% isn't quite right, but would be if all those tests had been performed "now".

[eatmadustch]

Originally posted by MikeH
Er...no. There are hopefully 12 more primes to find, thus if we were able to look to the future to the point where that 12th prime is found, the cumulative probability between now and then would be 1200%, thus greater than 100%.

But this can only be a prediction, so I'm not going to split hairs. I'm simply making the point that one in 290,000 feels too high, and that 0.29% isn't quite right, but would be if all those tests had been performed "now".

I still don't think that there will ever be 100% (until we actually find the prime(s)). We are talking about if all the tests are perfomed "now". That means that every time you complete a test you will have the possibility of one in 108000 that that test is prime. The next test also has a possibility of one in 108000 that it's prime, so does the next. So the chance that out of x tests you will have at least one prime is not x/108000, that is how many you could expect on average. The possibility of finding a least one prime is 1-(the possibility of not finding a single prime), so it's 1-(107999/108000)^x! This is of course assuming that the possibility of finding a prime is not affected by the previous test (so it also isn't exact)

[wblipp]

Originally posted by smh
..I think you shouldn't count the weight of the number because thats already reflected in the sieving. Numbers with a lower weight have more candidates removed by sieving already.

I flipped over to the Resouce Allocation thread to review the study I had done comparing Merten's Theorem with the sieving experience. There I got good agreement with the experience leaving the Proth Weights in. So then I sat down to think about it for a while.

Proth Weights describe how the divisibiliity of a proth sequence differs from the divisibility of a sequence of consecutive integers. For example, with consecurtive integers, 1/2 are divisible by 2, 1/3 of the rest are divisible by 3, etc. So we can think of the probability of being prime as the end result of (1/2)*(2/3)*(4/5)... . But for proth sequences, none are devisible by 2, 1/2 of the remainder are divisible by 3, one fourth of the remainder are divisible by 5. So the sequence should start (1)*(1/2)*(3/4)... The detalis vary depending on the k values - sometimes 1/3 are divisible by 7 and sometimes none. Sometimes the ones diviible by 11 are always divisible by 3, so we get no new sieving.

Merten's Theorem tells us about the results when sieving blocks of consecutive integers. We need to include the Proth Weight to adjust this to the effects of seiving consecutive proth numbers instead of consecutive integers. So I think both the Proth Weight and Merten's Theorem belong in the estimate.

EDIT - Proth Weights belong in both Merten's Theorem and in the Prime Number Theorem's probability. They cancel, so this is the same as not having it at all. I goofed and got the Proth Weight in only one part. The corrected number is one test in 47,000.

[smh]

http://groups.yahoo.com/group/primeform/message/3260

[wblipp]

Originally posted by smh
..I think you shouldn't count the weight of the number because thats already reflected in the sieving. Numbers with a lower weight have more candidates removed by sieving already.

Mea Culpa. I"m wrong and you're kinda right. The probability any unsieved test case is prime is a proth-weighted Prime Number probability. 0.163/ln(x) - I was right about that.

The probability a number remains after sieving is a proth-weighted Merten's Theorem. Our SoB Sieving results clearly shows this and I got that part wrong.

The probability a test that we actually perform is prime is the ratio of these two numbers. Taking the ratio with Proth Weights in both parts is the same as taking the ratio with Proth Weights in neither part - this identity is what people are talking about when they say that deep sieving wipes out proth weights.

So let's fix this model:

We are handing out tests around 3.7 million. Our average k value is about 27000, so the average value is about x=27000*2^3700000. If we were testing every number in this size range, we would expect to find primes about 1/ln(x) - about one every 2.6 million.

But these are Proth numbers with low Proth Weight. Our average proth weight is about .163. If we were testing all Proth numbers, the probability of finding a prime would be .163/ln(x), about once every 16 million tests.

But the Sieving is mostly completed through 23x10^12. Merten's Theorem tells us that if we were sieving consecutive integers, the fraction of remaining numbers should be exp(-gamma)/ln(23*10^12), about 1 in 55.

But the Proth weight of 0.163 applies to Merten's theorem, too. So the fraction of proth numbers remaining should be about 1 in 340

So the chance that one of the trials we really conduct will find a prime is about one in 47,000.