Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • jtrjtrjtr2001
    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
    • 0 Attachment
      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,
      Sarad.
    • Phil Carmody
      ... 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
      • 0 Attachment
        --- 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
      • Jens Kruse Andersen
        ... 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
        • 0 Attachment
          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
        • Jack Brennen
          ... 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
          • 0 Attachment
            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
          • Phil Carmody
            ... Good catch, Jack! Phil () ASCII ribbon campaign () Hopeless ribbon campaign / against HTML mail / against gratuitous bloodshed
            Message 5 of 6 , Sep 14, 2007
            • 0 Attachment
              --- 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
            • Jens Kruse Andersen
              ... 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
              • 0 Attachment
                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
                http://tech.groups.yahoo.com/group/yg-alerts/message/24 has not been
                completely fixed yet. I'm currently posting through
                http://tech.groups.yahoo.com/group/primenumbers/ where I haven't seen
                a long delay.

                --
                Jens Kruse Andersen
              Your message has been successfully submitted and would be delivered to recipients shortly.