mersenneforum.org Probability of finding a factor
 Register FAQ Search Today's Posts Mark Forums Read

 2004-06-23, 11:15 #12 Axel Fox     May 2003 9610 Posts Ok, you guys got me thinking a bit hard, my probability and combinatorics skills seem to be a bit rusty. Sorry for the confusion.
 2004-06-23, 11:25 #13 Axel Fox     May 2003 1408 Posts BTW BTW : If you guys are right (and after some thinking, I think you are) then the probability of finding a factor between X and Y bits is (approximately) (Y-X)/(Y-1) Maybe this should be put on the site under the 1/X thingy, to avoid this discussion to repeat itself in the future.
2004-06-23, 13:00   #14
markr

"Mark"
Feb 2003
Sydney

13×43 Posts

Quote:
 Originally Posted by Axel Fox (Y-X)/(Y-1)
Neat!

2004-06-24, 00:58   #15
jinydu

Dec 2003
Hopefully Near M48

33368 Posts

Quote:
 Originally Posted by MrHappy We believe that - we don't know it.
Actually, I mentioned in some other thread that the 1/x formula is itself an approximation and CANNOT be THE correct formula.

If it was THE correct formula, there would be a 100% chance of finding a factor between 2 (2^1) and 4 (2^2), which obviously isn't true.

 2004-06-24, 01:30 #16 JuanTutors     Mar 2004 3·167 Posts So the trial factoring part is essentially settled with this approximation: ASSUMING that, through trial factoring, the probability of finding a factor between 2^x and 2^(x+1) is 1/x for any Mersenne number, so that the probability of NOT finding a factor is (x-1)/x, the probability of findng a factor between 2^62 and 2^68 is 1-(61/62)*(62/63)*...*(66/67) = 1-61/67 = 6/67 = 8.96%. I have no reason to believe whether it is actually higher or lower than this. I won't even ask the data people to do some sort of check on that. However, I would guess that, for this range, the number of possible factors of M_p declines linearly as growth in the prime p in M_p, since possible factors must be of the form 2kp+1. This is good enough though, and I'm too busy to try to find a more rigorous formula. Plus, I would have trouble arguing that any simple-enough formula would be accurate for such a small range. Now about the second part of the question, I don't know if anyone should bother. In about 4 weeks I will start a new P-1 factoring on M33844211. I'll set it my RAM allocation to 200 MB and see what happens.
 2004-06-24, 01:56 #17 Axel Fox     May 2003 6016 Posts Well, I'm not really interested that much in a correct formula either, nor do the others in this discussion, I think. I just like to discuss about mathematical stuff and maybe learn something out of it here and there. Good luck on the P-1 factoring
 2004-09-26, 02:37 #18 JuanTutors     Mar 2004 3×167 Posts From the statement on www.mersenne.org that the probability of finding a factor between 2^x and 2^(x+1) is 1/x, we got the formula that the probability of finding a factor between 2^x and 2^y is 1 - (x-1)/(y-1). I was just wondering whether anyone has created a script to check whether that estimate has held up so far. My reason is pretty lame...I'm a little to the left on the bell curve, b/c it took me 19 TFs to find a factor. I also haven't found any through 12 P-1 trials
 2004-09-26, 03:32 #19 jinydu     Dec 2003 Hopefully Near M48 2×3×293 Posts I've noticed that, unfortunately, the Primenet account report doesn't keep track of the number of TF's attempted, only the number of factors found and the number of CPU years. Why is that?
 2004-09-26, 08:06 #20 garo     Aug 2002 Termonfeckin, IE 251010 Posts Yes, do a search on the forum and there are some posts from over a year ago where the numbers were verified and came pretty close to acurrate. But remember these are probabilities and you could be lucky or unlucky. If you are factoring numbers from 2^62->2^67 then the probability that you won't find a factor in 19 tries is about 22% jinydu: That was a design decision taken several years ago. And yes we all think it was unfortunate. But then hindsight is 20/20.
 2004-09-26, 09:47 #21 Matthias C. Noc     Dec 2003 23×3 Posts Of the 18 exponents (all in the 25M-26M range) I found in the recent weeks 6 factors, one in 62, three in 63 and two in 65 bit range. Best, Matthias C. Noch

 Similar Threads Thread Thread Starter Forum Replies Last Post nuggetprime Math 2 2011-03-19 22:14 optim Math 2 2003-12-06 19:03 eepiccolo Math 4 2003-06-07 05:56 Deamiter Math 4 2002-12-25 06:06 Deamiter Software 4 2002-10-11 16:36

All times are UTC. The time now is 23:05.

Thu Oct 29 23:05:34 UTC 2020 up 49 days, 20:16, 1 user, load averages: 2.33, 2.32, 2.30