mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2004-06-23, 11:15   #12
Axel Fox
 
Axel Fox's Avatar
 
May 2003

9610 Posts
Default

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 is offline   Reply With Quote
Old 2004-06-23, 11:25   #13
Axel Fox
 
Axel Fox's Avatar
 
May 2003

1408 Posts
Default 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.
Axel Fox is offline   Reply With Quote
Old 2004-06-23, 13:00   #14
markr
 
markr's Avatar
 
"Mark"
Feb 2003
Sydney

13×43 Posts
Default

Quote:
Originally Posted by Axel Fox
(Y-X)/(Y-1)
Neat!
markr is offline   Reply With Quote
Old 2004-06-24, 00:58   #15
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

33368 Posts
Default

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.
jinydu is offline   Reply With Quote
Old 2004-06-24, 01:30   #16
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

3·167 Posts
Default

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.
JuanTutors is offline   Reply With Quote
Old 2004-06-24, 01:56   #17
Axel Fox
 
Axel Fox's Avatar
 
May 2003

6016 Posts
Default

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
Axel Fox is offline   Reply With Quote
Old 2004-09-26, 02:37   #18
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

3×167 Posts
Default

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
JuanTutors is offline   Reply With Quote
Old 2004-09-26, 03:32   #19
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2×3×293 Posts
Default

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?
jinydu is offline   Reply With Quote
Old 2004-09-26, 08:06   #20
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

251010 Posts
Default

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.
garo is offline   Reply With Quote
Old 2004-09-26, 09:47   #21
Matthias C. Noc
 
Matthias C. Noc's Avatar
 
Dec 2003

23×3 Posts
Default

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
Matthias C. Noc is offline   Reply With Quote
Reply

Thread Tools


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

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

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