20040621, 22:49  #1 
Mar 2004
111101001_{2} Posts 
Probability of finding a factor
For some of the math people who maybe know something about the software, what is the approximate probability of finding a factor of M34000009 if you trial factor from 2^62 to 2^68 and you give @200Mb of ram to the P1 factoring?

20040622, 23:36  #2 
Mar 2004
1E9_{16} Posts 
Should this be in the Programming or Math section instead?

20040623, 00:19  #3 
Jun 2004
UK
10001011_{2} Posts 
http://mersenne.org/math.htm says that the probability of finding a factor between 2^x and 2^(x+1) is 1/x.
So if we're trialfactoring between 62 and 68 then the chance we don't find a factor is 61/62 * 62/63 * ... * 67/68 which simplifies to 61/68. The chance of finding a factor between 62 and 68 is 7/68. Someone will correct me if I made any mistakes. 
20040623, 01:11  #4 
May 2003
2^{5}×3 Posts 
Actually your chance is
1/62 + 1/63 + 1/64 + 1/65 + 1/66 + 1/67 which is (using a calculator) roughly 9.31 % 
20040623, 01:54  #5 
Jun 2004
UK
139 Posts 
That's the chance a factor exists in just 1 of those ranges. It's possible a factor exists between 62 and 63 and another factor exists between 65 and 66 which means you're very slightly underestimating the chances.

20040623, 02:19  #6  
Nov 2003
3·5·11 Posts 
Quote:
As for Angel Fox, you have calculated the expected number of factors, not the probability of finding a factor. If you don't believe your answer is wrong, try doing the same calculation if you are factoring to a very large number of bits. You will find you get n answer greater than one, which is clearly not a probability. 

20040623, 02:33  #7 
May 2003
2^{5}·3 Posts 
I know that nfortino, but given a number of probabilities Pi for i=1..n, the probability that one of the cases 1..n is true is P1+P2+P3 ... +Pn and normally, the sum of all Pi for every possible i is 1.
However, the given probability of 1/X is only an aproximation, not a real probability and that is why you (eventually) get a number greater than 1. The series 1/X + 1/X+1 + 1/X+2 ... is even a part of the harmonic series and if I'm not mistaking that series diverges (goes to infinity if you go to X=infinity). So, if you factor to infinity bits, that would mean (by your definition of 1/X being the number of factors) that a certain number would have an infinite number of factors, which is also not true. Both of these contradiction result from the fact that 1/X is only an approximation and not a real probability function. 
20040623, 04:14  #8 
Aug 2002
Ann Arbor, MI
433 Posts 
Axel Fox: The probability of finding a factor doesn't add up to one......if it did, that would kinda make it hard to find primes
Secondly, you can't just add the probabilities. Can I roll a 6sided die 7 times and have a 116.666666666% chance of rolling a 6? Also, why exactly would we factor to infinite bits? Methinks any factoring past p bits would be a might bit redundant... My thinking is that P(finding factor)=1P(not finding factor)=1[(61/62)*(62/63)*(63/64)...*(67/68)]=7/68 
20040623, 05:43  #9  
"William"
May 2003
New Haven
2·3^{2}·131 Posts 
Quote:


20040623, 06:19  #10 
"Mark"
Feb 2003
Sydney
3·191 Posts 
Let's see if I can help clarify  or only confuse!
Kevin & marc: you have the right approach, but seven parts in your calculation where there should be six  the number of intervals between 62 & 68. The last part is the chance of not finding a factor between 67 & 68: 66/67. So the probability is 6/67 = 8.9552% Axel Fox: the sum of all Pi is only 1 if the events don't overlap. When the program finds a factor, it stops & doesn't look in higher ranges. So P(factor found between 63 & 64) is actually P(factor exists between 63 & 64).P(no factor exists between 62 & 63), and so on. Just to check, I worked it out: P(factor found between 62 & 68) = P(factor between 62 & 63) + P(no factor between 62 & 63).P(factor between 63 & 64) + P(no factor between 62 & 64).P(factor between 64 & 65) + ... + P(no factor between 62 & 67).P(factor between 67 & 65) = 1/62 + (61/62).(1/63) + (61/62).(62/63).(1/64) + ... + (61/62).(62/63).(63/64).(64/65).(65/66).(1/67) which is numerically the same as 6/67. [I used a spreadsheet... ] That last part should have helped confuse! 
20040623, 08:00  #11  
Dec 2003
Paisley Park & Neverland
5×37 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Probability of factor (TF)  nuggetprime  Math  2  20110319 22:14 
probability of finding a Mersenne prime  optim  Math  2  20031206 19:03 
Probability of finding a factor in TF  eepiccolo  Math  4  20030607 05:56 
Probability of finding a factor in DC p1  Deamiter  Math  4  20021225 06:06 
Probability of finding a prime number  Deamiter  Software  4  20021011 16:36 