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

Re: [PrimeNumbers] p-1 isn't a random integer

Expand Messages
  • mikeoakes2@aol.com
    In a message dated 04/02/2005 01:54:40 GMT Standard Time, decio@decpp.net writes: So, if we re looking for an accurate numerical value of the probability that
    Message 1 of 3 , Feb 4, 2005
    • 0 Attachment
      In a message dated 04/02/2005 01:54:40 GMT Standard Time, decio@...
      writes:

      So, if we're looking for an accurate
      numerical value of the probability that a random integer near n is prime,
      shouldn't we use the heuristic 1.123/log n instead?


      No, we shouldn't.

      >by Mertens theorem, the probability that an integer [n] isn't
      >divisible by any primes up to x is exp(-gamma)/log x

      This is true for integers n >> x.
      But fails when x gets as large as sqrt(n).

      -Mike Oakes


      [Non-text portions of this message have been removed]
    • Décio Luiz Gazzoni Filho
      As expected, my idea proposed below is not new. David Broadhurst and Phil Carmody (both missed members of this list, unlike the Goldbach-proving spammers)
      Message 2 of 3 , Feb 4, 2005
      • 0 Attachment
        As expected, my idea proposed below is not new. David Broadhurst and Phil
        Carmody (both missed members of this list, unlike the Goldbach-proving
        spammers) pointed me towards the twin-prime constant C2 = 0.660162, which is
        the ratio between Mertens' product and `my' product below. One can use
        Cohen's methods from http://www.math.u-bordeaux.fr/~cohen/hardylw.dvi to
        compute C2 to high-precision, as pointed out by David Broadhurst. Mike Oakes
        also pointed out (off list) an interesting site regarding the twin-prime
        constant, the page by Xavier Gourdon at
        http://numbers.computation.free.fr/Constants/Primes/twin.html. If this isn't
        enough, the owners of Crandall & Pomerance's book can have a look at chapter
        1, who has a derivation of the twin prime conjecture.

        Décio

        On Thursday 03 February 2005 23:49, you wrote:
        > For p prime, the integer p-1 is an important quantity in certain analyses
        > (particularly if they involve the group (Z/pZ)*), but as I recall, this
        > integer is usually considered as `a random integer in the vicinity of p' in
        > such analyses (except perhaps by considering that it is even).
        >
        > However, a neat idea occurred to me: just as the probability that 2 divides
        > this integer is skewed in comparison to a random integer (it's 1 in this
        > case but 1/2 for a random integer), so is the probability that it is
        > divisible by any other prime. Consider for instance the residue class of p
        > mod 3; unless p itself is 3, then p == 1 or 2 mod 3, with equal probability
        > for each residue class. So p-1 == 0 or 1 mod 3 also with equal probability.
        > Thus, p-1 is divisible by 3 with probability 1/2, not 1/3 as expected.
        > Using the same argument, p-1 is divisible by a given prime q with
        > probability 1/(q-1), not 1/q.
        >
        > The first implication that occurred to me is that one shouldn't use
        > Mertens' theorem in any analyses involving p-1 where p is prime. For
        > instance, I computed the probability that primes from 3 to 31337 divide a
        > given integer using Mertens' theorem; the result is 0.1085. Using PARI/GP
        > to evaluate the product (1 - 1/(p-1)) for primes p from 3 to 31337, I
        > obtained 0.07157. The difference is quite real.
        >
        > I'll try to work out an estimate, similar to Mertens' theorem, but for the
        > product (1 - 1/(p-1)) instead. However, I'm pretty sure David Broadhurst or
        > Mike Oakes will beat me to it (:
        >
        > I don't know how useful this is (probably not useful at all), but I thought
        > it was neat and worth mentioning.


        [Non-text portions of this message have been removed]
      Your message has been successfully submitted and would be delivered to recipients shortly.