Probability of finding a factor - Page 2

Axel Fox · 2004-06-23, 11:15

Ok, you guys got me thinking a bit hard, my probability and combinatorics skills seem to be a bit rusty. Sorry for the confusion.

Axel Fox · 2004-06-23, 11:25

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.

markr · 2004-06-23, 13:00

Quote:

Originally Posted by Axel Fox

(Y-X)/(Y-1)

Neat!

jinydu · 2004-06-24, 00:58

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.

JuanTutors · 2004-06-24, 01:30

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.

Axel Fox · 2004-06-24, 01:56

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

JuanTutors · 2004-09-26, 02:37

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

jinydu · 2004-09-26, 03:32

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?

garo · 2004-09-26, 08:06

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.

Matthias C. Noc · 2004-09-26, 09:47

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

2004-06-23, 11:25	#13
Axel Fox May 2003 2⁵·3 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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Probability of factor (TF)	nuggetprime	Math	2	2011-03-19 22:14
probability of finding a Mersenne prime	optim	Math	2	2003-12-06 19:03
Probability of finding a factor in TF	eepiccolo	Math	4	2003-06-07 05:56
Probability of finding a factor in DC p-1	Deamiter	Math	4	2002-12-25 06:06
Probability of finding a prime number	Deamiter	Software	4	2002-10-11 16:36

2004-06-23, 11:15	#12
Axel Fox May 2003 1100000₂ 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-24, 01:30	#16
JuanTutors "Juan Tutors" Mar 2004 230₁₆ 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 2⁵·3 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 "Juan Tutors" Mar 2004 2⁴×5×7 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 101011010000₂ 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 18₁₆ 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