Browse Groups

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

(3)
• NextPrevious
• 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
View Source
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]
• 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 1 of 3 , Feb 4, 2005
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.