Statistical odds for prime in Wagstaff vs Mersenne

[diep]

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, VRB-Reix 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

[R.D. Silverman]

Originally Posted by diep

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

What do you mean by "i (sic) was so lucky to find"?
What does luck have to do with your finding a published result?
Unless, of course, you were conducting a random search.

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.

A number is either prime or it isn't. There are no odds.

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?

At a website i found somewhere i vaguely remember that chance for a prime in Mersenne between n and 2n is e ^ eta.

This statement is grossly wrong. It is so wrong that even with your
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 pre-college 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]

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.

This above statement is total gibberish. It is devoid of any mathematical
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.

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.

This question is yet more gibberish. What do you mean by "difference
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 well-known
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.

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.

You have no business claiming a "gutfeeling". You know nothing about
this subject whatsover. You are completely clueless about even
basic probability theory as evidenced by:

Mersenne has P( prime between [n..2n] ) = e^eta

Once again, a PROBABILITY CAN NOT BE GREATER THAN ONE.

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

No, nothing you say makes sense. Before you can even hope
to discuss this subject intelligently, you MUST take a course
in basic statistical theory and probability, along with a semester
of number theory.

[diep]

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

[R.D. Silverman]

Originally Posted by diep

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.

What you write above is still gibberish. However, I understand the
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^n-1) is prime is total nonsense.
And it is provably wrong via known theorems.

Now initially it happens to be a lucky formula, but at bigger bitdepths it seems to get less lucky.

You continue to bandy words without any understanding of what you
are saying. What is a "lucky formula"??? Define it!

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

It makes very vague sense. But it is wrong.

[Mini-Geek]

The chances of something about the size of (2^n)/3 being prime is about 1/ln((2^n)/3)=1/(ln(2)*n-ln(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.

[R.D. Silverman]

Originally Posted by Mini-Geek

The chances of something about the size of (2^n)/3 being prime is about 1/ln((2^n)/3)=1/(ln(2)*n-ln(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.

Allowing for a loose interpretation of the word "chances"
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.

[diep]

Originally Posted by R.D. Silverman

Allowing for a loose interpretation of the word "chances"
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.

Obviously i'm interested in a formula that can produce per tested exponent just as much primes on average as mersenne.

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.

[diep]

Originally Posted by R.D. Silverman

What you write above is still gibberish. However, I understand the
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^n-1) is prime is total nonsense.
And it is provably wrong via known theorems.



You continue to bandy words without any understanding of what you
are saying. What is a "lucky formula"??? Define it!



It makes very vague sense. But it is wrong.

sir, when software gets more mature searching for industry grade prime candidates, it will get more gibberish of course.

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 VRB-Reix 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.

[R.D. Silverman]

Originally Posted by diep

Obviously i'm interested in a formula that can produce per tested exponent just as much primes on average as mersenne.

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.


p.s. i'll write that speech myself i guess considering the used language here.

Look up "Poisson Distribution" and "Erlang Distribution". Study them. When
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.

[R.D. Silverman]

Originally Posted by diep

sir, when software gets more mature searching for industry grade prime candidates, it will get more gibberish of course.

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 VRB-Reix 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.

Congratulations. You just convinced me that further discussion with you
is pointless. You are willfully ignorant and choose to remain so.

I am putting you on my ignore list.

<plonk>

[CRGreathouse]

Originally Posted by R.D. Silverman

A number is either prime or it isn't. There are no odds.

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?

I don't think that's what the OP intended. It seems clear (s)he's looking for something similar to what Mini-Geek posted. Let me attempt to formalize this.

"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.