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

Re: [PrimeNumbers] probability of (2*p1*p2) + 1 being prime

Expand Messages
  • 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 1 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 2 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 3 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 4 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.