20091216, 16:04  #1 
Sep 2006
The Netherlands
787 Posts 
Statistical odds for prime in Wagstaff vs Mersenne
hi all,
I didn't study math so i really am interested in viewpoints others here for something i pondered upon this weekend. We have been searching now for a while for Wagstaff. Now of course i was so lucky to find the PRP P = (2^986191 + 1) / 3 In fact Wagstaff if we look as close as possible to 2^n, which is 2^n + 1, then we search for a factorisation P1 * P2 of 2^n + 1 of P1 = 3 and P2 some unknown. Now i didn't study math, let alone number theory, a lot (my study was computer science so i had relative little math, basically only some stuff that's interesting to prove lemma's). Ok all disclaimers aside. Basically i'd like to discuss the odds for a prime. When i say prime i mean either a 100% prime or an 'industry grade' prime, which is a PRP. As we know with current public standings of math, VRBReix test has not been proven as delivering primes yet. So when i refer to primes in this message i mean either probable primes or 100% primes, as the statistical odds of course is so tiny that a probable prime appears to be not prime in these million bits ranges, that we can neglect it for the calculation what odds is for a prime. At a website i found somewhere i vaguely remember that chance for a prime in Mersenne between n and 2n is e ^ eta. Now i first want to get rid about the 1 versus +1 discussion. Some argue that odds for a 1 formula to deliver primes is in a more consistent manner than +1 formula's. I realize this all too well. The question i like to raise therefore has to do with the difference between a formula F = k * 2^n + 1, with small k, delivering a direct prime P versus F = k * 2^n + 1, with small k, delivering a combined P1 * P2 where both P1 and P2 are prime. Now there is more combinations possible of course for P1 * P2 than there is possibilities for P. However in case of Wagstaff we speak about a constant P1 which is 3. My gutfeeling is that one needs to test more numbers there to find a prime than with a similar formula. In this case the similar formula is Mersenne. Mersenne has P( prime between [n..2n] ) = e^eta Now i take into account the possibility that a formula searching for a combined P1 * P2 with given P1 has for each P1 average odds is P( prime between [n..2n] ) = e^eta / P1 Does this make sense? Thanks, Vincent 
20091216, 16:51  #2  
"Bob Silverman"
Nov 2003
North of Boston
2×3×29×43 Posts 
Quote:
What does luck have to do with your finding a published result? Unless, of course, you were conducting a random search. Quote:
The "probability" that arises really means the following. I have tested a number for primality with an algorithm that sometimes produces incorrect answers. It has declared a number to be prime. What is the probability that the ALGORITHM gave me the wrong answer? Quote:
disclaimer about not having studied mathematics, I have to wonder if you are clueless. You *MUST* have studied at least some secondary school math! For a > 0, a^x is greater than 1 for all x > 0. This is a basic fact of precollege mathematics. If you don't even know this level of math, then I suggest that you go back and relearn what you failed to learn in your secondary school education. Otherwise, you will have ZERO hope of understanding any discussion about computational number theory. Now, since e > 1 and (what you call) eta > 0, e^eta is greater than 1. If you don't know that probabilities can not be greater than 1, you have no business discussing this subject at all. Now, what is true, is that if certain conjectures are true, then the expected number of Mersenne primes between 2^n and 2^(n+1) is e^(gamma) as n >oo. [gamma is Euler's constant]. Note carefully, the last condition: as n>oo. For any FINITE interval [2^n, 2^(n+1)] for finite n, we do not know the number of expected Mersenne primes in this interval. We know that as n gets very large that we can approximate the number of expected primes by e^gamma, but there is no way to know how good the approximation is. We have no way to quantify the meaning of 'n gets very large'. Such a statement would take the form: For all n > M, [for some determined value of M], The expected number of primes in the interval [2^n, 2^(n+1)] is exp(gamma + o(1)) where o(1) depends on M. But we don't know the value of o(1) for any M. You claim to have studied computer science. I therefore assume that you know the meaning of the o(1) notation. [It arises in the study of algorithms] Quote:
meaning whatsoever. The phrase "more consistent manner" is totally meaningless. Your statement about "getting rid of the 1 versus +1" discussion is meaningless. The above paragraph is just word salad. Quote:
between a formula"? What is a "direct prime P"? What is the difference between a prime and a "direct Prime"?? What is a "delivering a combined P1* p2"? How does a formula "deliver" this??? If you mean that F is the product of exactly two primes, then SAY THAT. DON'T INVENT TERMINOLOGY. Are you asking the following: For k chosen uniformly at random in the interval [A,B], what is the probability that : k*2^n + 1 is prime? k*2^n  1 is prime? k*2^n + 1 is the product of exactly two primes? k*2^n  1 is the product of exactly two primes? These questions can be answered only if certain wellknown conjectures are true. We can give answers to these questions based on some heuristic arguments, but no proofs exist and we don't know if the heuristics are correct. Furthermore, any approximations to these probabilities would only be correct as either n>oo or A>oo. In fact, for fixed n we can give a fully proved estimate for the above probabilities along with an accurate assessment of the possible error in the estimate. Quote:
this subject whatsover. You are completely clueless about even basic probability theory as evidenced by: Quote:
Quote:
to discuss this subject intelligently, you MUST take a course in basic statistical theory and probability, along with a semester of number theory. 

20091216, 17:08  #3 
Sep 2006
The Netherlands
1423_{8} Posts 
Of course my main question you ignore.
Which is the idea that Wagstaff has an average expectation according to my guess of 1/3 the expectation of Mersenne because it requires P=3 at the formula as the first prime. Now initially it happens to be a lucky formula, but at bigger bitdepths it seems to get less lucky. If i politically formulate it like next, does it make sense? So in the same domain where there is 3 mersenne primes to be expected there is 1 or less wagstaffs to be expected statistically. Does that make sense to you? Vincent 
20091216, 17:25  #4  
"Bob Silverman"
Nov 2003
North of Boston
2×3×29×43 Posts 
Quote:
general gist of the question. You DID NOT ask this in your original post. And the idea is wrong. Even if one uses a vague "handwaving" notion of probability, the idea that the "probability" that (2^n+1)/3 is prime equals 1/3 of the probability that (2^n1) is prime is total nonsense. And it is provably wrong via known theorems. Quote:
are saying. What is a "lucky formula"??? Define it! Quote:


20091216, 17:33  #5 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
2×3×23×31 Posts 
The chances of something about the size of (2^n)/3 being prime is about 1/ln((2^n)/3)=1/(ln(2)*nln(3)). The chances of something about the size of 2^n being prime is about 1/ln(2^n)=1/(ln(2)*n). ln is the base e logarithm.
I'm not sure if any known or conjectured things regarding Mersenne or Wagstaff numbers would throw off what you're considering, or even if that's what you're asking, but maybe that helps anyway. 
20091216, 17:42  #6  
"Bob Silverman"
Nov 2003
North of Boston
1110100111010_{2} Posts 
Quote:
This is closer to the truth. But the "probabilities" are not 1/ln(2^n) (resp.) 1/ln(2^n/3). They will be C1 * 1/ln(2^n) and C2 * 1/ln(2^n/3) where C1 and C2 are constants given by infinite products. And it is definitely NOT the case that C2 = 1/3 C1. I don't think that the OP knows enough math to even know what it is that he is asking. His ideas about basic probability theory are total nonsense. 

20091216, 18:15  #7  
Sep 2006
The Netherlands
787 Posts 
Quote:
Now that we are approaching 2 million digits, testing far over 1 million digits, some teammember gets nervous as the previous one found is a 300k digits. Factor 6 difference nearly. I understand his worry. Even a junkie isn't that long without dope. This is how you should read my post and not different. So if you can confirm that C1=C2 or very close to it, then maybe in combination with an inspiring speech that keeps us on track. Thanks, Vincent p.s. i'll write that speech myself i guess considering the used language here. 

20091216, 18:28  #8  
Sep 2006
The Netherlands
787 Posts 
Quote:
If i look to approximation search i'm busy completing now for game tree search it is combining about a 1000 algorithms and enhancements just within 1 single search, many of which not published yet working brilliantly. Compared to non gibberish searches that dominated in 80s, the current search of my software (apart from its evaluation function that has of course huge progress) is searching for the holy grail reaching easily depths of factor 2 to 3 deeper than in 80s would be possible with same hardware. Compared to that the quest for PRP's so far is rather push button technology. Currently we have a 2 phase form of search. First trial factoring then the VRBReix test gets performed. I'd argue that much of the fun is the future prospect to add more phases to that such as a factorisation phase after the trial factoring using some gibberish produced by me. Without gibberish no fun. 

20091216, 18:33  #9  
"Bob Silverman"
Nov 2003
North of Boston
7482_{10} Posts 
Quote:
you feel that you can give a good, RIGOROUS description of them, get back to us. [and don't just parrot someone else's description] Maybe then we can have an intelligent discussion. There is simply too much that you don't know now. I will give a hint: sometimes primes of special form will "come in bunches" and sometimes there will be a "wide gap between them". This is the nature of a Poisson distribution. [and many other distributions as well] So you are looking near 2 million digits and the last one was around 300K. SO WHAT??? Don't make the mistake of believing that statistical trends that apply "in the long run" must also apply "in the short run". Don't make the mistake of believing that the failure of an event to occur makes it more likely that it will occur in the near future. This is just plain WRONG. Last fiddled with by R.D. Silverman on 20091216 at 18:34 Reason: fix long lines 

20091216, 18:36  #10  
"Bob Silverman"
Nov 2003
North of Boston
2×3×29×43 Posts 
Quote:
is pointless. You are willfully ignorant and choose to remain so. I am putting you on my ignore list. <plonk> 

20091216, 19:14  #11  
Aug 2006
5987_{10} Posts 
Quote:
"What is the probability that f(n) is prime?" is an outfix operator (Z ⟶ Z) ⟶ ([x, ∞) ⟶ [0, 1]) for some real number x. The operand f(n) has a dummy variable n. If the limit of f(n) as n increases without bound does not exist, or is not +infinity, then "What is the probability that f(n) is prime?" ⟼ (R ⟼ 0). (Or else undefined; there are many possibilities at this point.) Otherwise, let g(f(n), k) be a function (Z ⟶ Z, Z) ⟶ {0, 1} such that g(f(n), k) = 0 if , where the outfix . is the cardinality, and let C be where the infix a%b is the least nonnegative residue of a mod b and the product is taken over primes p. Then "What is the probability that f(n) is prime?" ⟼ C / log f(n), where the implicit x is the least x for which log f(y) ≥ C for all y ≥ x. There is a natural connection between the function "What is the probability that f(n) is prime?" and the question "What is the probability that f(n) is prime?", though of course the two are distinct. Last fiddled with by CRGreathouse on 20091216 at 19:24 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Odds of prime discussion  TheCount  Conjectures 'R Us  30  20140908 15:26 
30th Wagstaff prime  T.Rex  Math  0  20070904 07:10 
odds of a random prime being a number  ewmayer  Lounge  10  20070801 20:11 
Silverman & Wagstaff on Joint Distribution of Ultimate and Penultimate Prime Factors  wblipp  Math  12  20060402 18:40 
Statistical Investigation of Large Digit Mersenne Primes . . . (please don't bite me)  9021951  Math  29  20050315 16:26 