## probability of (2*p1*p2) + 1 being prime

Expand Messages
• Hi, Let p2 be a large prime. We find another large random prime p1, such that y = (2*p1*p2) + 1. Is there any way, one could quantify the probability of y
Message 1 of 6 , Sep 8, 2007
Hi,

Let p2 be a large prime. We find another large random prime p1, such that
y = (2*p1*p2) + 1.

Is there any way, one could quantify the probability of y being a prime?

By 'large' primes, it is meant that p1 and p2 are primes, such that
finding the complete prime factorization of y is computationally
infeasible.

Thank you,
• ... Well, it s just like any arbitrary number of the same size except that it s even, it s not divisible by p1, and it s not divisible by p2. Therefore there s
Message 2 of 6 , Sep 9, 2007
--- jtrjtrjtr2001 <jtrjtrjtr2001@...> wrote:
> Hi,
>
> Let p2 be a large prime. We find another large random prime p1, such that
> y = (2*p1*p2) + 1.
>
> Is there any way, one could quantify the probability of y being a prime?

Well, it's just like any arbitrary number of the same size except that
it's even, it's not divisible by p1, and it's not divisible by p2.
Therefore there's a prime density boost of (2/1) * (p1/(p1-1)) * (p2/(p2-1))
Those final two factors are effectively 1.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

____________________________________________________________________________________
Sick sense of humor? Visit Yahoo! TV's
Comedy with an Edge to see what's on, when.
http://tv.yahoo.com/collections/222
• ... Phil meant y is odd, but another factor must also be considered. If q is a random odd prime other than p1 and p2, then q does not divide y-1. q must divide
Message 3 of 6 , Sep 9, 2007
Phil Carmody wrote:
> --- jtrjtrjtr2001 <jtrjtrjtr2001@...> wrote:
>> Let p2 be a large prime. We find another large random prime p1, such that
>> y = (2*p1*p2) + 1.
>>
>> Is there any way, one could quantify the probability of y being a prime?
>
> Well, it's just like any arbitrary number of the same size except that
> it's even, it's not divisible by p1, and it's not divisible by p2.
> Therefore there's a prime density boost of (2/1) * (p1/(p1-1)) *
> (p2/(p2-1))
> Those final two factors are effectively 1.

Phil meant y is odd, but another factor must also be considered.
If q is a random odd prime other than p1 and p2, then q does
not divide y-1. q must divide one of the q-1 numbers from
y to y+q-2, and the chance that q divides y increases from
1/q to 1/(q-1).
So the chance that q does not divide changes from
(q-1)/q to (q-2)/(q-1), which corresponds to multiplying the
chance by ((q-2)/(q-1)) / ((q-1)/q) = q*(q-2)/(q-1)^2.

The situation is just like twin primes:
If p is a large prime then p+2 is odd. If q is a random odd
prime other than p then q does not divide p, so the chance
of q dividing p+2 increases from 1/q to 1/(q-1).

The twin prime constant C_2 = 0.66016... is the product
over all odd primes q of q*(q-2)/(q-1)^2
See for example http://mathworld.wolfram.com/TwinPrimesConstant.html

A random large number n has chance 1/log(n) of being prime.
Our y is odd and also taking C_2 into consideration changes
the chance to 2*C_2/log(y).

--
Jens Kruse Andersen
• ... And y is not congruent to 1 mod 3, or to 1 mod 5, or to 1 mod 7, etc. Which should make y somewhat more likely to be divisible by these small numbers...
Message 4 of 6 , Sep 9, 2007
Phil Carmody wrote:
> --- jtrjtrjtr2001 <jtrjtrjtr2001@...> wrote:
>> Hi,
>>
>> Let p2 be a large prime. We find another large random prime p1, such that
>> y = (2*p1*p2) + 1.
>>
>> Is there any way, one could quantify the probability of y being a prime?
>
> Well, it's just like any arbitrary number of the same size except that
> it's even, it's not divisible by p1, and it's not divisible by p2.
> Therefore there's a prime density boost of (2/1) * (p1/(p1-1)) * (p2/(p2-1))
> Those final two factors are effectively 1.
>

And y is not congruent to 1 mod 3, or to 1 mod 5, or to 1 mod 7, etc.

Which should make y somewhat more likely to be divisible by these small
numbers... For instance, half of a random sample of y values should be
divisible by 3.

So I think that the actual density boost would be 2 times the twin prime
constant (~ 0.66) which would make these y numbers about 1.32 times
more likely to be prime than arbitrary numbers of the same size.

Jack
• ... Good catch, Jack! Phil () ASCII ribbon campaign () Hopeless ribbon campaign / against HTML mail / against gratuitous bloodshed
Message 5 of 6 , Sep 14, 2007
--- Jack Brennen <jb@...> wrote:
> Phil Carmody wrote:
> > --- jtrjtrjtr2001 <jtrjtrjtr2001@...> wrote:
> >> Hi,
> >>
> >> Let p2 be a large prime. We find another large random prime p1, such that
> >> y = (2*p1*p2) + 1.
> >>
> >> Is there any way, one could quantify the probability of y being a prime?
> >
> > Well, it's just like any arbitrary number of the same size except that
> > it's even, it's not divisible by p1, and it's not divisible by p2.
> > Therefore there's a prime density boost of (2/1) * (p1/(p1-1)) *
> (p2/(p2-1))
> > Those final two factors are effectively 1.
> >
>
> And y is not congruent to 1 mod 3, or to 1 mod 5, or to 1 mod 7, etc.

Good catch, Jack!

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

____________________________________________________________________________________
Got a little couch potato?
Check out fun summer activities for kids.
http://search.yahoo.com/search?fr=oni_on_mail&p=summer+activities+for+kids&cs=bz
• ... All 4 above posts were mailed September 9 but it took 5 days to deliver the posts by Jack and I. We are far apart and the posts showed up the same minute
Message 6 of 6 , Sep 14, 2007
September 9 jtrjtrjtr2001 wrote:
> y = (2*p1*p2) + 1.

Phil Carmody wrote:
> > Well, it's just like any arbitrary [odd] number of the same size

I wrote:
> If q is a random odd prime other than p1 and p2,
> then q does not divide y-1

Jack Brennen wrote:
> And y is not congruent to 1 mod 3, or to 1 mod 5,
> or to 1 mod 7, etc.

All 4 above posts were mailed September 9 but it took 5 days to
deliver the posts by Jack and I. We are far apart and the posts
showed up the same minute so it seems like a Yahoo problem.
http://tech.groups.yahoo.com/group/primeform/message/8788 was delayed
from August 31 to September 5. Maybe the problem from