20110126, 02:33  #1 
"James Heinrich"
May 2004
exNorthern Ontario
13×233 Posts 
Probability of TF per bit level
The answer is probably on the forums somewhere (pretty sure I remember reading it years ago), but I was unable to find it.
How do you calculate the probability of finding a trial factor for exponent between 2^A and 2^B? 
20110126, 03:02  #2 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
79×109 Posts 
From http://v5www.mersenne.org/various/math.php
Looking at past factoring data we see that the chance of finding a factor between 2^{X} and 2^{X+1} is about 1/x. Last fiddled with by Uncwilly on 20110126 at 03:05 
20110126, 03:29  #3 
"James Heinrich"
May 2004
exNorthern Ontario
13×233 Posts 
Ah, that's where it's hiding! Thanks Uncwilly.
Does this look like a reasonable set of probabilities for TF to various bit levels? Code:
2^2 += 50.000% = 50.000% 2^3 += 33.333% = 66.667% 2^4 += 25.000% = 75.000% 2^5 += 20.000% = 80.000% 2^6 += 16.667% = 83.333% 2^7 += 14.286% = 85.714% 2^8 += 12.500% = 87.500% 2^9 += 11.111% = 88.889% 2^10 += 10.000% = 90.000% 2^11 += 9.091% = 90.909% 2^12 += 8.333% = 91.667% 2^13 += 7.692% = 92.308% 2^14 += 7.143% = 92.857% 2^15 += 6.667% = 93.333% 2^16 += 6.250% = 93.750% 2^17 += 5.882% = 94.118% 2^18 += 5.556% = 94.444% 2^19 += 5.263% = 94.737% 2^20 += 5.000% = 95.000% 2^21 += 4.762% = 95.238% 2^22 += 4.545% = 95.455% 2^23 += 4.348% = 95.652% 2^24 += 4.167% = 95.833% 2^25 += 4.000% = 96.000% 2^26 += 3.846% = 96.154% 2^27 += 3.704% = 96.296% 2^28 += 3.571% = 96.429% 2^29 += 3.448% = 96.552% 2^30 += 3.333% = 96.667% 2^31 += 3.226% = 96.774% 2^32 += 3.125% = 96.875% 2^33 += 3.030% = 96.970% 2^34 += 2.941% = 97.059% 2^35 += 2.857% = 97.143% 2^36 += 2.778% = 97.222% 2^37 += 2.703% = 97.297% 2^38 += 2.632% = 97.368% 2^39 += 2.564% = 97.436% 2^40 += 2.500% = 97.500% 2^41 += 2.439% = 97.561% 2^42 += 2.381% = 97.619% 2^43 += 2.326% = 97.674% 2^44 += 2.273% = 97.727% 2^45 += 2.222% = 97.778% 2^46 += 2.174% = 97.826% 2^47 += 2.128% = 97.872% 2^48 += 2.083% = 97.917% 2^49 += 2.041% = 97.959% 2^50 += 2.000% = 98.000% 2^51 += 1.961% = 98.039% 2^52 += 1.923% = 98.077% 2^53 += 1.887% = 98.113% 2^54 += 1.852% = 98.148% 2^55 += 1.818% = 98.182% 2^56 += 1.786% = 98.214% 2^57 += 1.754% = 98.246% 2^58 += 1.724% = 98.276% 2^59 += 1.695% = 98.305% 2^60 += 1.667% = 98.333% 2^61 += 1.639% = 98.361% 2^62 += 1.613% = 98.387% 2^63 += 1.587% = 98.413% 2^64 += 1.563% = 98.438% 2^65 += 1.538% = 98.462% 2^66 += 1.515% = 98.485% 2^67 += 1.493% = 98.507% 2^68 += 1.471% = 98.529% 2^69 += 1.449% = 98.551% 2^70 += 1.429% = 98.571% 2^71 += 1.408% = 98.592% 2^72 += 1.389% = 98.611% 2^73 += 1.370% = 98.630% 2^74 += 1.351% = 98.649% 2^75 += 1.333% = 98.667% 2^76 += 1.316% = 98.684% 2^77 += 1.299% = 98.701% 2^78 += 1.282% = 98.718% 2^79 += 1.266% = 98.734% 2^80 += 1.250% = 98.750% 2^81 += 1.235% = 98.765% 2^82 += 1.220% = 98.780% 2^83 += 1.205% = 98.795% 2^84 += 1.190% = 98.810% 2^85 += 1.176% = 98.824% 2^86 += 1.163% = 98.837% 2^87 += 1.149% = 98.851% 2^88 += 1.136% = 98.864% 2^89 += 1.124% = 98.876% 2^90 += 1.111% = 98.889% Last fiddled with by James Heinrich on 20110126 at 03:48 
20110126, 12:00  #4  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1E0C_{16} Posts 
Quote:
It's not merely empirical; it's analytically derived. The proof was in some thread a few years ago Quote:
First, understand that the 1/x probability of finding one factor does not necessarily refer to a case where there are only two factors. Next, the series 1/1 + 1/2 + 1/3 + 1/4 + ... is divergent. As x increases, the sum up to 1/x increases, and goes past 100%, then 200%, then 300%, ... Third, since the form of Mersenne (2^{p}1) factors is 2kp+1, the probability of a factor in the interval 2^{x} and 2^{x+1} is actually zero until 2^{x+1} exceeds 2p+1 (the smallest possible candidate factor). As long as 2^{x} < 2p+1, there can be no factor less than 2^{x}. Thus, trial factoring can never, ever, hope to find a factor until it searches in the range above 2^{floor(log[sub]2[/sub] p)+1}. (For example, an initial TF run up to 2^31 on a Mersenne number with exponent above 2 billion is practically instantaneous and proves nothing because it will never find a factor.) Last fiddled with by cheesehead on 20110126 at 12:20 

20110126, 14:08  #5  
"James Heinrich"
May 2004
exNorthern Ontario
101111010101_{2} Posts 
First, thank you for taking the time to correct and enlighten me
Quote:
(actually, I'm not sure that the whole thing shouldn't be shifted up one level, so that 516000000 => 80?) Quote:
Quote:
Quote:
Quote:
Does this make more sense? Code:
function TFprobability($exponent, $bits1, $bits2) { $chance = 0; $bits1 = max($bits1, floor(log($exponent, 2)) + 1); if ($bits2 > $bits1) { for ($i = $bits1; $i < $bits2; $i++) { $chance += (1 / $bits1); } } return $chance; } Code:
M53656597 TF to 2^1 = 0.0% M53656597 TF to 2^2 = 0.0% M53656597 TF to 2^3 = 0.0% M53656597 TF to 2^4 = 0.0% M53656597 TF to 2^5 = 0.0% M53656597 TF to 2^6 = 0.0% M53656597 TF to 2^7 = 0.0% M53656597 TF to 2^8 = 0.0% M53656597 TF to 2^9 = 0.0% M53656597 TF to 2^10 = 0.0% M53656597 TF to 2^11 = 0.0% M53656597 TF to 2^12 = 0.0% M53656597 TF to 2^13 = 0.0% M53656597 TF to 2^14 = 0.0% M53656597 TF to 2^15 = 0.0% M53656597 TF to 2^16 = 0.0% M53656597 TF to 2^17 = 0.0% M53656597 TF to 2^18 = 0.0% M53656597 TF to 2^19 = 0.0% M53656597 TF to 2^20 = 0.0% M53656597 TF to 2^21 = 0.0% M53656597 TF to 2^22 = 0.0% M53656597 TF to 2^23 = 0.0% M53656597 TF to 2^24 = 0.0% M53656597 TF to 2^25 = 0.0% M53656597 TF to 2^26 = 0.0% M53656597 TF to 2^27 = 3.8% M53656597 TF to 2^28 = 7.7% M53656597 TF to 2^29 = 11.5% M53656597 TF to 2^30 = 15.4% M53656597 TF to 2^31 = 19.2% M53656597 TF to 2^32 = 23.1% M53656597 TF to 2^33 = 26.9% M53656597 TF to 2^34 = 30.8% M53656597 TF to 2^35 = 34.6% M53656597 TF to 2^36 = 38.5% M53656597 TF to 2^37 = 42.3% M53656597 TF to 2^38 = 46.2% M53656597 TF to 2^39 = 50.0% M53656597 TF to 2^40 = 53.8% M53656597 TF to 2^41 = 57.7% M53656597 TF to 2^42 = 61.5% M53656597 TF to 2^43 = 65.4% M53656597 TF to 2^44 = 69.2% M53656597 TF to 2^45 = 73.1% M53656597 TF to 2^46 = 76.9% M53656597 TF to 2^47 = 80.8% M53656597 TF to 2^48 = 84.6% M53656597 TF to 2^49 = 88.5% M53656597 TF to 2^50 = 92.3% M53656597 TF to 2^51 = 96.2% M53656597 TF to 2^52 = 100.0% M53656597 TF to 2^53 = 103.8% M53656597 TF to 2^54 = 107.7% M53656597 TF to 2^55 = 111.5% M53656597 TF to 2^56 = 115.4% M53656597 TF to 2^57 = 119.2% M53656597 TF to 2^58 = 123.1% M53656597 TF to 2^59 = 126.9% M53656597 TF to 2^60 = 130.8% M53656597 TF to 2^61 = 134.6% M53656597 TF to 2^62 = 138.5% M53656597 TF to 2^63 = 142.3% M53656597 TF to 2^64 = 146.2% M53656597 TF to 2^65 = 150.0% M53656597 TF to 2^66 = 153.8% M53656597 TF to 2^67 = 157.7% M53656597 TF to 2^68 = 161.5% M53656597 TF to 2^69 = 165.4% M53656597 TF to 2^70 = 169.2% M53656597 TF to 2^71 = 173.1% M53656597 TF to 2^72 = 176.9% M53656597 TF to 2^73 = 180.8% M53656597 TF to 2^74 = 184.6% M53656597 TF to 2^75 = 188.5% M53656597 TF to 2^76 = 192.3% M53656597 TF to 2^77 = 196.2% M53656597 TF to 2^78 = 200.0% M53656597 TF to 2^79 = 203.8% M53656597 TF to 2^80 = 207.7% M53656597 TF to 2^81 = 211.5% M53656597 TF to 2^82 = 215.4% M53656597 TF to 2^83 = 219.2% M53656597 TF to 2^84 = 223.1% M53656597 TF to 2^85 = 226.9% M53656597 TF to 2^86 = 230.8% M53656597 TF to 2^87 = 234.6% M53656597 TF to 2^88 = 238.5% M53656597 TF to 2^89 = 242.3% Last fiddled with by James Heinrich on 20110126 at 14:11 

20110126, 14:50  #6  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17×251 Posts 
Quote:
You should be adding expected factors, not the probability of finding a factor. For small amounts, such as most single bit levels, these two figures are about the same, but the exact formula for expected factors F given the probability of at least one factor P, is F=log(1P). (I should note that I'm not sure whether 1/x probability or 1/x expected factors is closer to the truth, but GIMPS's Math page implies it's the probability, not the expected factors) When you expect y factors in a range (or any other approximately Poissondistributed random events), the probability of at least 1 factor is about 1(e^(y)) (which you can see, from looking at the formula in that link for the probability of exactly k occurrences, as being the probability of not having 0 factors, or 1[probability of having exactly 0 factors]). As y grows, the probability of at least 1 factor approaches 1 (100%), but never reaches it. e.g. in your example, from 1 to 2^78, you estimate a 200% probability of a factor at some point, which of course doesn't make sense. I think a more accurate statement would be to expect 2 factors, which gives a ~86.5% probability of at least one factor. I also suspect that the usual 1/x probability doesn't apply in the lowest possible bit levels, due to the extremely low number of k's that make potential factors. But there's also the fact that "if a Sophie Germain prime p is congruent to 3 (mod 4), then its matching safe prime 2p + 1 will be a divisor of the Mersenne number 2^p1" (quote from the linked Wikipedia article). It should be possible to look at GIMPS stats to draw some decent conclusions regarding this, but I don't know off hand of an easy way to do it. Last fiddled with by MiniGeek on 20110126 at 15:09 

20110126, 18:18  #7  
"James Heinrich"
May 2004
exNorthern Ontario
13×233 Posts 
Quote:
Transcribing that formula I get this: Code:
function PoissonProbability($occurances, $expected_number) { $e = M_E; // 2.718281828459 $k = $occurances; $Y = $expected_number; return (pow($Y, $k) * pow($e, $Y)) / factorial($k); } But I'm not sure what to feed it to get your ~86.5% result? 

20110126, 18:31  #8  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17·251 Posts 
Quote:
Code:
function PoissonProbability($expected_number) { $e = M_E; // 2.718281828459 return 1pow($e, $expected_number); } Last fiddled with by MiniGeek on 20110126 at 18:41 

20110126, 18:54  #9 
"James Heinrich"
May 2004
exNorthern Ontario
13×233 Posts 
Oooh, now I'm getting there!
This is what I have now: Code:
function PoissonProbability($expected_number) { return 1  pow(M_E, $expected_number); } function TFprobability($exponent, $bits1, $bits2) { $expected = 0; $bits1 = max($bits1, floor(log($exponent, 2)) + 1); if ($bits2 > $bits1) { for ($i = $bits1; $i < $bits2; $i++) { $expected += (1 / $bits1); } } return PoissonProbability($expected); } Code:
M53656597 TF to 2^1: expected=0.00; prob=0.000% M53656597 TF to 2^2: expected=0.00; prob=0.000% M53656597 TF to 2^3: expected=0.00; prob=0.000% M53656597 TF to 2^4: expected=0.00; prob=0.000% M53656597 TF to 2^5: expected=0.00; prob=0.000% M53656597 TF to 2^6: expected=0.00; prob=0.000% M53656597 TF to 2^7: expected=0.00; prob=0.000% M53656597 TF to 2^8: expected=0.00; prob=0.000% M53656597 TF to 2^9: expected=0.00; prob=0.000% M53656597 TF to 2^10: expected=0.00; prob=0.000% M53656597 TF to 2^11: expected=0.00; prob=0.000% M53656597 TF to 2^12: expected=0.00; prob=0.000% M53656597 TF to 2^13: expected=0.00; prob=0.000% M53656597 TF to 2^14: expected=0.00; prob=0.000% M53656597 TF to 2^15: expected=0.00; prob=0.000% M53656597 TF to 2^16: expected=0.00; prob=0.000% M53656597 TF to 2^17: expected=0.00; prob=0.000% M53656597 TF to 2^18: expected=0.00; prob=0.000% M53656597 TF to 2^19: expected=0.00; prob=0.000% M53656597 TF to 2^20: expected=0.00; prob=0.000% M53656597 TF to 2^21: expected=0.00; prob=0.000% M53656597 TF to 2^22: expected=0.00; prob=0.000% M53656597 TF to 2^23: expected=0.00; prob=0.000% M53656597 TF to 2^24: expected=0.00; prob=0.000% M53656597 TF to 2^25: expected=0.00; prob=0.000% M53656597 TF to 2^26: expected=0.00; prob=0.000% M53656597 TF to 2^27: expected=0.04; prob=3.773% M53656597 TF to 2^28: expected=0.08; prob=7.404% M53656597 TF to 2^29: expected=0.12; prob=10.898% M53656597 TF to 2^30: expected=0.15; prob=14.260% M53656597 TF to 2^31: expected=0.19; prob=17.495% M53656597 TF to 2^32: expected=0.23; prob=20.608% M53656597 TF to 2^33: expected=0.27; prob=23.603% M53656597 TF to 2^34: expected=0.31; prob=26.486% M53656597 TF to 2^35: expected=0.35; prob=29.260% M53656597 TF to 2^36: expected=0.38; prob=31.929% M53656597 TF to 2^37: expected=0.42; prob=34.497% M53656597 TF to 2^38: expected=0.46; prob=36.969% M53656597 TF to 2^39: expected=0.50; prob=39.347% M53656597 TF to 2^40: expected=0.54; prob=41.635% M53656597 TF to 2^41: expected=0.58; prob=43.838% M53656597 TF to 2^42: expected=0.62; prob=45.957% M53656597 TF to 2^43: expected=0.65; prob=47.996% M53656597 TF to 2^44: expected=0.69; prob=49.958% M53656597 TF to 2^45: expected=0.73; prob=51.846% M53656597 TF to 2^46: expected=0.77; prob=53.663% M53656597 TF to 2^47: expected=0.81; prob=55.411% M53656597 TF to 2^48: expected=0.85; prob=57.094% M53656597 TF to 2^49: expected=0.88; prob=58.713% M53656597 TF to 2^50: expected=0.92; prob=60.271% M53656597 TF to 2^51: expected=0.96; prob=61.770% M53656597 TF to 2^52: expected=1.00; prob=63.212% M53656597 TF to 2^53: expected=1.04; prob=64.600% M53656597 TF to 2^54: expected=1.08; prob=65.936% M53656597 TF to 2^55: expected=1.12; prob=67.221% M53656597 TF to 2^56: expected=1.15; prob=68.458% M53656597 TF to 2^57: expected=1.19; prob=69.648% M53656597 TF to 2^58: expected=1.23; prob=70.793% M53656597 TF to 2^59: expected=1.27; prob=71.895% M53656597 TF to 2^60: expected=1.31; prob=72.956% M53656597 TF to 2^61: expected=1.35; prob=73.976% M53656597 TF to 2^62: expected=1.38; prob=74.958% M53656597 TF to 2^63: expected=1.42; prob=75.903% M53656597 TF to 2^64: expected=1.46; prob=76.812% M53656597 TF to 2^65: expected=1.50; prob=77.687% M53656597 TF to 2^66: expected=1.54; prob=78.529% M53656597 TF to 2^67: expected=1.58; prob=79.339% M53656597 TF to 2^68: expected=1.62; prob=80.119% M53656597 TF to 2^69: expected=1.65; prob=80.869% M53656597 TF to 2^70: expected=1.69; prob=81.591% M53656597 TF to 2^71: expected=1.73; prob=82.285% M53656597 TF to 2^72: expected=1.77; prob=82.954% M53656597 TF to 2^73: expected=1.81; prob=83.597% M53656597 TF to 2^74: expected=1.85; prob=84.216% M53656597 TF to 2^75: expected=1.88; prob=84.811% M53656597 TF to 2^76: expected=1.92; prob=85.384% M53656597 TF to 2^77: expected=1.96; prob=85.936% M53656597 TF to 2^78: expected=2.00; prob=86.466% M53656597 TF to 2^79: expected=2.04; prob=86.977% M53656597 TF to 2^80: expected=2.08; prob=87.468% M53656597 TF to 2^81: expected=2.12; prob=87.941% M53656597 TF to 2^82: expected=2.15; prob=88.396% M53656597 TF to 2^83: expected=2.19; prob=88.834% M53656597 TF to 2^84: expected=2.23; prob=89.255% M53656597 TF to 2^85: expected=2.27; prob=89.661% M53656597 TF to 2^86: expected=2.31; prob=90.051% M53656597 TF to 2^87: expected=2.35; prob=90.426% M53656597 TF to 2^88: expected=2.38; prob=90.788% M53656597 TF to 2^89: expected=2.42; prob=91.135% M53656597 TF to 2^90: expected=2.46; prob=91.470% M53656597 TF to 2^91: expected=2.50; prob=91.792% M53656597 TF to 2^92: expected=2.54; prob=92.101% M53656597 TF to 2^93: expected=2.58; prob=92.399% M53656597 TF to 2^94: expected=2.62; prob=92.686% M53656597 TF to 2^95: expected=2.65; prob=92.962% M53656597 TF to 2^96: expected=2.69; prob=93.228% M53656597 TF to 2^97: expected=2.73; prob=93.483% M53656597 TF to 2^98: expected=2.77; prob=93.729% M53656597 TF to 2^99: expected=2.81; prob=93.966% 
20110126, 19:20  #10  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Quote:
Quote:
Quote:
I think that there needs to be further refinement to take account of the digital effect as exponents pass a poweroftwo. (Our custom of TFing between exact powers of two is an artificial one.) As it stands, the same expectation and probability is calculated for any exponent for which floor(log($exponent, 2)) is the same value, but I don't think that's realistic. (Yes, I introduced the floor, but it was to make a different point.) Perhaps what's happening is that the 1/x approximation was okay for integrating over many values, but as we examine specific cases it needs to be replaced by a different function that approaches 1/x as a limit. But I'm speculating about things I don't know. Last fiddled with by cheesehead on 20110126 at 19:47 

20110126, 19:48  #11 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
10AB_{16} Posts 
I think it'd be more accurate to do "$expected += log(1  (1 / $bits1));". This is so that you're incrementing the number of expected factors by the number of expected factors for that bit level, not by the probability of a factor in that bit level. As for where that equation came from: it's 1(e^Y)=P solved for Y: Y=log(1P). It's a pretty small difference, but there is a difference, e.g. in your newest example at 2^99 the numbers are expected=2.81; prob=93.966%, but with that change it's 2.86 and 94.291%, respectively. In any case, you're definitely on the right track now!
Yes, I agree. Not sure how to fix it, and it's probably even more minor than the thing I just pointed out, but ideally it should be fixed. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
TF bit level  davieddy  Puzzles  71  20131222 07:26 
ECM level program  henryzz  GMPECM  8  20120915 17:00 
any mid level sequence left?  firejuggler  Aliquot Sequences  5  20120209 11:02 
Reliability and confidence level  lidocorc  Information & Answers  6  20090811 04:04 
Factors appearing at level 62  ric  Lone Mersenne Hunters  7  20050906 12:12 