mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2021-04-12, 16:41   #1
drkirkby
 
"David Kirkby"
Jan 2021
Althorne, Essex, UK

449 Posts
Default 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.
So that's a range of numbers between
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=1-probability_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 =

1-probability_of_all_composite
1-0.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?
drkirkby is offline   Reply With Quote
Old 2021-04-12, 19:13   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

23×19×71 Posts
Default

I think that the error is in the mprime display. Your value feels right.
Uncwilly is offline   Reply With Quote
Old 2021-04-12, 23:09   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

3·5·107 Posts
Default

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 P-1 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 2021-04-12 at 23:10 Reason: typo
R. Gerbicz is offline   Reply With Quote
Old 2021-04-13, 09:26   #4
drkirkby
 
"David Kirkby"
Jan 2021
Althorne, Essex, UK

449 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Your error is in the assumptation that mp is prime by 1/log(mp) probability. .
Yes, I also rather stupidly ignored that for Mersenne Prime testing, one is only testing odd numbers, so the probability of a random odd number being prime is 2/log(mp), not 1/log(mp). But that only changes my original estimate by a factor of 2, which is still a factor of 45 different to mprime.

Quote:
Originally Posted by R. Gerbicz View Post
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 P-1 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.
I'm not following all that, but I get that the probability 2^p -1 being prime is higher than predicted by the Prime Number Theorem as various tests have been done to eliminate easy cases - there's also the fact that we only test odd numbers. .

Dave

Last fiddled with by drkirkby on 2021-04-13 at 09:46 Reason: Removed paragraph about factors of a random integer, as it deserves another thread
drkirkby is offline   Reply With Quote
Old 2021-04-13, 12:58   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

3·5·107 Posts
Default

Quote:
Originally Posted by drkirkby View Post
Yes, I also rather stupidly ignored that for Mersenne Prime testing, one is only testing odd numbers, so the probability of a random odd number being prime is 2/log(mp), not 1/log(mp). But that only changes my original estimate by a factor of 2, which is still a factor of 45 different to mprime.
I've written a quite different formula. At least one PRP/LL test has performed on each prime for p<10^8.
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
Even if you multiple it by two, you are still very far from the true number.

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
?
It is quite good, because (as we know M2 is prime) this says that the expected number of Mersenne primes is 52.08, and we know
51 [a double check still can find one or more]. That is impressive. Returning to your problem:

Code:
? p=1.1e7;
? 1-(1-prob(p)*log(p)/log(2^76))^32
%5 = 3.8894933977891824505859557809830582239 E-5
? 
? 1/%5
%6 = 25710.289174636665666484139748462123138
This is how Maths works. Not far from the original number, used the same setup p=1.1e8 and 2^76 TF limit, but not
included the P-1 works. Still the probability is close to the program's number.
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
P-1 finding multiple factors at once? mnd9 PrimeNet 2 2019-12-04 16:27
Maximize chances of finding Mersenne Prime dennisonprime Information & Answers 7 2016-11-10 07:52
option for finding multiple factors during trial factoring tha Software 24 2014-06-10 23:31
Testing exponents smaller than latest prime? HuzursuZ PrimeNet 3 2005-03-09 06:16
Chances of finding a factor with ECM smh Factoring 16 2004-03-30 18:49

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


Sat Dec 10 01:43:38 UTC 2022 up 113 days, 23:12, 0 users, load averages: 1.11, 0.91, 0.81

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔