20210412, 16:41  #1 
"David Kirkby"
Jan 2021
Althorne, Essex, UK
449 Posts 
How do I calculate chances of finding a prime, while testing multiple exponents?
First, my background is engineering, not mathematics, and I'm not too hot on maths.
I'm trying to understand how mprime calculates the chances of finding a prime in one of the exponents I'm testing at the minute. I'm testing 32 exponents between M110274583 and M110904847. This is what mprime shows. Code:
Below is a report on the work you have queued and any expected completion dates. <snip> The chance that one of the 32 exponents you are testing will yield a Mersenne prime is about 1 in 26429. 2^110274583 1 = 1.74x10^33195957 2^110904847 1 = 4.09x10^33385685 The mean of those is around 2x10^33385685 The probability of any one of them being prime is then probability_of_one_being_prime=1/log(n)=1/log(2x10^33385685)=1.3x10^8 The probability of one being composite is then probability_of_one_being_composite=1probability_of_one_being_prime =0.9999999869915960129554356230753 Testing 32, I would expect the probability of them all being composite to be probability_of_all_composite=probability_of_one_being_composite^32 =0.99999958373115634697586958993 Probability of at least one being prime = 1probability_of_all_composite 10.99999958373115634697586958993 =4.2x10^7 So I would expect the chance of finding a prime to be one in 1/4.2x10^7 = 2.4x10^6. Yet mprime says the chance of finding a Mersenne prime is 1 in 26429, which is about 90 times higher than I calculate at 1 in 2400000. Clearly I'm doing something wrong, as I calculate the chances of finding a prime are about 90x worse than mprime. I realise that the fact that the exponents have been trial factored increases the chances of finding a prime compared to a random number, but does that account for all the difference? 
20210412, 19:13  #2 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
2×3^{3}×199 Posts 
I think that the error is in the mprime display. Your value feels right.

20210412, 23:09  #3 
"Robert Gerbicz"
Oct 2005
Hungary
2·3·263 Posts 
Your error is in the assumptation that mp is prime by 1/log(mp) probability. The true is that it is prime by a "much" larger probability: c*log(log(mp))/log(mp) probability [what is constant*log(p)/p], for c see https://primes.utm.edu/notes/faq/NextMersenne.html . Here in the search for Mersenne primes you even have a higher chance to find a prime, because these Mp values survived trial factoring (TF), and most of them some P1 factoring works.
ps. it doesn't mean that it is a golden treasure in all possible way, because Mp's prime divisors are in the q=2*k*p+1 form, so you basically lost that log(log(mp)) factor in TF. Last fiddled with by R. Gerbicz on 20210412 at 23:10 Reason: typo 
20210413, 09:26  #4  
"David Kirkby"
Jan 2021
Althorne, Essex, UK
449 Posts 
Quote:
Quote:
Dave Last fiddled with by drkirkby on 20210413 at 09:46 Reason: Removed paragraph about factors of a random integer, as it deserves another thread 

20210413, 12:58  #5  
"Robert Gerbicz"
Oct 2005
Hungary
1578_{10} Posts 
Quote:
Lets check out what your original formula says about the number of Mersenne primes for p in [2,10^8]: Code:
? s=0;forprime(p=2,10^8,s+=1/(p*log(2)));s %1 = 4.5805210191516384202989894082293513116 Setting the exact conjectured formula for p>2: Code:
? prob(p)=exp(0.57721)*log(if(p%4==1,6,2)*p)/(p*log(2)) %2 = (p)>exp(0.57721)*log(if(p%4==1,6,2)*p)/(p*log(2)) ? ? ? s=0;forprime(p=3,10^8,s+=prob(p));s %3 = 51.085172813343511293322996421505390399 ? 51 [a double check still can find one or more]. That is impressive. Returning to your problem: Code:
? p=1.1e7; ? 1(1prob(p)*log(p)/log(2^76))^32 %5 = 3.8894933977891824505859557809830582239 E5 ? ? 1/%5 %6 = 25710.289174636665666484139748462123138 included the P1 works. Still the probability is close to the program's number. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
P1 finding multiple factors at once?  mnd9  PrimeNet  2  20191204 16:27 
Maximize chances of finding Mersenne Prime  dennisonprime  Information & Answers  7  20161110 07:52 
option for finding multiple factors during trial factoring  tha  Software  24  20140610 23:31 
Testing exponents smaller than latest prime?  HuzursuZ  PrimeNet  3  20050309 06:16 
Chances of finding a factor with ECM  smh  Factoring  16  20040330 18:49 