mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Data > mersenne.ca

Reply
 
Thread Tools
Old 2021-06-13, 12:58   #1
Zhangrc
 
"University student"
May 2021
北京

22×32 Posts
Default Is the "Combined" factoring probability actually wrong on mersenne.ca?

The "Combined" probability just add the trial factoring probability and the P-1 factoring probability, but that makes no sense.
Take 108071849 for example:
It has been trial factored to 2^77, with 64.9351% chance of finding a factor. Also, the chance of finding a factor in P-1 with b1=755000, b2=21551000 assuming no factor below 2^77 is 3.5775% (a conditional probability).
Let A denote the event of "finding a factor below 2^77"
B denote the event of "finding a factor in P-1 with b1=755000, b2=21551000"
then P(A) = 64.9351%, P(B|(!A)) = P(!A && B) / P(!A) = 3.5775%
So the total probability of finding a factor should be
P(A || B) = P(A) +P(!A && B) = P(A) + P(B|(!A)) * P(!A) = P(A) + P(B|(!A)) * (1-P(!A)) = 0.0649351 + 0.035775 * (1-0.649351) = 66.1895%
Which makes sense.
This formula can also avoid having over 113% probability (???) on exponents such as 1277.
(PS: I'm only a freshman student studying probability. If my formula is wrong, please point out :)

Last fiddled with by Zhangrc on 2021-06-13 at 12:59
Zhangrc is online now   Reply With Quote
Old 2021-06-14, 00:52   #2
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

65358 Posts
Default

Quote:
Originally Posted by Zhangrc View Post
The "Combined" probability just add the trial factoring probability and the P-1 factoring probability, but that makes no sense.
It probably doesn't. But I'm just a programmer who runs the site, my math knowledge is poor.

If others agree that your implementation makes sense I'm happy to revise the site accordingly.
But I'll need a little more explanation in simple terms what you mean with the logical combinations of probabilities, such as P(!A && B) or P(B|(!A))
James Heinrich is offline   Reply With Quote
Old 2021-06-14, 03:25   #3
Zhangrc
 
"University student"
May 2021
北京

2416 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
It probably doesn't. But I'm just a programmer who runs the site, my math knowledge is poor.

If others agree that your implementation makes sense I'm happy to revise the site accordingly.
But I'll need a little more explanation in simple terms what you mean with the logical combinations of probabilities, such as P(!A && B) or P(B|(!A))
maybe I should use TEX.
Attached Thumbnails
Click image for larger version

Name:	捕获.JPG
Views:	42
Size:	72.4 KB
ID:	25111  

Last fiddled with by Zhangrc on 2021-06-14 at 03:52
Zhangrc is online now   Reply With Quote
Old 2021-06-14, 03:53   #4
Zhangrc
 
"University student"
May 2021
北京

22×32 Posts
Default

Quote:
Originally Posted by Zhangrc View Post
The "Combined" probability just add the trial factoring probability and the P-1 factoring probability, but that makes no sense.
Take 108071849 for example:
It has been trial factored to 2^77, with 64.9351% chance of finding a factor. Also, the chance of finding a factor in P-1 with b1=755000, b2=21551000 assuming no factor below 2^77 is 3.5775% (a conditional probability).
Let A denote the event of "finding a factor below 2^77"
B denote the event of "finding a factor in P-1 with b1=755000, b2=21551000"
then P(A) = 64.9351%, P(B|(!A)) = P(!A && B) / P(!A) = 3.5775%
So the total probability of finding a factor should be
P(A || B) = P(A) +P(!A && B) = P(A) + P(B|(!A)) * P(!A) = P(A) + P(B|(!A)) * (1-P(!A)) = 0.0649351 + 0.035775 * (1-0.649351) = 66.1895%
Which makes sense.
This formula can also avoid having over 113% probability (???) on exponents such as 1277.
(PS: I'm only a freshman student studying probability. If my formula is wrong, please point out :)
Sorry for a typo. The formula should be 0.649351 + 0.035775 * (1-0.649351) = 66.1895% (There was a redundant 0)
Zhangrc is online now   Reply With Quote
Old 2021-06-14, 04:01   #5
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

342110 Posts
Default

Quote:
Originally Posted by Zhangrc View Post
maybe I should use TEX.
Unfortunately that means about the same to me as this.
Attached Thumbnails
Click image for larger version

Name:	Hieroglyphs.jpg
Views:	36
Size:	67.3 KB
ID:	25112  
James Heinrich is offline   Reply With Quote
Old 2021-06-14, 04:03   #6
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

D5D16 Posts
Default

Quote:
Originally Posted by Zhangrc View Post
Sorry for a typo. The formula should be 0.649351 + 0.035775 * (1-0.649351) = 66.1895% (There was a redundant 0)
Would that always equate to

CombinedProb = TFprob + (PM1prob * (1 - TFprob))

? If so, I can work with that.
James Heinrich is offline   Reply With Quote
Old 2021-06-14, 04:07   #7
Zhangrc
 
"University student"
May 2021
北京

22×32 Posts
Default

It seems so. But you'd better wait for another one who really knows the stuff and states that the formula is correct.
Zhangrc is online now   Reply With Quote
Old 2021-06-14, 06:03   #8
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

25338 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
Would that always equate to

CombinedProb = TFprob + (PM1prob * (1 - TFprob))

? If so, I can work with that.
Let's consider a story: on a dangerous trip, somebody must first cross a lake, and afterwards the forest. In the lake there's an aligator that would eat him with 90% chances. In the unlikely event that he successfully crosses the lake, he must now face a tiger in the forest, which would eat him with 60% chances. What are the chances that the person perishes in this adventure?

A) the chances of being eaten by the tiger is: "60% of 10%" == 0.6 * 0.1 == 6% (because, if the aligator gets him first, the tiger is out of luck). Overall being eaten is: 90% + 6%, 96%.

B) considering the complement: surviving the whole trip means: not being eaten by the crocodile (10%), AND not being eaten by the tiger (40%). Surviving = 10% * 40% == 4%. The complement of surviving thus is 1 - 4% == 96%, same as above.

Last fiddled with by preda on 2021-06-14 at 06:10 Reason: spelling
preda is offline   Reply With Quote
Old 2021-06-14, 12:52   #9
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

D5D16 Posts
Default

Quote:
Originally Posted by preda View Post
Let's consider a story
So now I have hieroglyphs, crocodiles, and tigers.

I think what you're saying is that my simplified pseudocode above is correct, but please either confirm that it is, or provide a correction if it isn't.
James Heinrich is offline   Reply With Quote
Old 2021-06-14, 14:44   #10
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

262716 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
So now I have hieroglyphs, crocodiles, and tigers.
chalsall is offline   Reply With Quote
Old 2021-06-14, 15:42   #11
chris2be8
 
chris2be8's Avatar
 
Sep 2009

22×523 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
I think what you're saying is that my simplified pseudocode above is correct, but please either confirm that it is, or provide a correction if it isn't.
If the probability of finding a factor by P-1 is *independent* of the probability of finding a factor by TF then your pseudocode will be correct. But if P-1 could find factors that TF would also have found then that needs to be allowed for and I don't know how to do that.

In the normal case where both TF and P-1 have only a few% chance of finding a factor adding the probabilities would be nearly right. Which is probably why it's not been noticed until now.

Chris
chris2be8 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
What's wrong with PrimeGrid? I keep getting "The connection was reset"... Stargate38 Riesel Prime Search 3 2017-08-14 18:14
"factoring" vs "factorizing" ixfd64 Factoring 4 2012-10-16 04:07
Official "Benford was wrong!" thread Mini-Geek Aliquot Sequences 15 2009-06-18 19:09
P-1 factoring != "Mersenne numbers to factor"? James Heinrich Marin's Mersenne-aries 8 2004-05-17 11:09
trial factoring of "small" mersenne numbers antiroach Lone Mersenne Hunters 6 2003-07-16 23:35

All times are UTC. The time now is 09:44.


Sun Aug 1 09:44:12 UTC 2021 up 9 days, 4:13, 0 users, load averages: 1.76, 2.03, 2.17

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