Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It's known that the probability of selecting $ n $ natural numbers randomly and ending up with a greatest common divisor equal to one is $ \prod (1-p^{-n}) = 1/\zeta(n) $. However, a total GCD of 1 does not rule out any of the pairs among the set of $ n $ numbers sharing a common factor. What's the probability none of them share a common factor? (Since there's a possibility of "random selection" being ambiguous, let's take it to mean chosen with uniform probability from {$ 1,2,3,\dots, N$} as $N \to \infty $.)

share|improve this question
2  
A quick and dirty approach gives $\prod (1-1/p)^{n-1}(1+(n-1)/p)$. I don't know how to write this number in a "closed form". The (certainly not rigorous) idea is: for every prime $p$, the probability that $p$ divides a random number is $1/p$, and we can admit that it divides either none of the $n$ numbers (prob. $(1-1/p)^n$) or one of them ($(1-1/p)^{n-1}n/p$), and suppose that the probabilities for different $p$'s are independent. –  user8268 Jul 7 '11 at 10:03

1 Answer 1

up vote 7 down vote accepted

This answer is on a heuristical level; I don't purport to rigorously prove the result.

The probability $\prod (1-p^{-n})$ can be derived from the fact that for sufficiently large $N$ the probability of each number being divisible by a given prime $p$ is $p^{-1}$, so the probability of all $n$ numbers being thus divisible (which would lead to the gcd not being $1$) is $p^{-n}$. Applying this reasoning to your case, we have that the probability for not more than one of the $n$ numbers being divisible by $p$ is the sum of the probabilities of zero or one of them being divisible by $p$, which is

$$\binom n0\left(\frac{p-1}{p}\right)^n+\binom n1\left(\frac{p-1}{p}\right)^{n-1}\frac1p=\left(1-\frac1p\right)^{n-1}\left(1+\frac{n-1}p\right)\;.$$

So we could expect the probability you're looking for to be given by

$$p_n=\prod_p\left(1-\frac1p\right)^{n-1}\left(1+\frac{n-1}p\right)\;.$$

I don't know whether it's possible to evaluate this Euler product explicitly. Numerically (both evaluating the Euler product and generating large pseudo-random numbers), I get

$$ \begin{array}{|c|c|} n&p_n\\ \hline 1&1\\ 2&0.6079\\ 3&0.2867\\ 4&0.1149\\ 5&0.0409\\ \end{array} $$

Of course $p_2=1/\zeta(2)$, since in that case the two conditions coincide.

P.S.: The Euler product can be evaluated more efficiently numerically if we rewrite it as

$$p_{n+1}=\prod_p\left(1-\frac1p\right)^n\left(1+\frac np\right)=\prod_p\left(1-\frac1{p^2}\right)^n\frac{1+\frac np}{\left(1+\frac 1p\right)^n}=\zeta(2)^{-n} \prod_p\frac{1+\frac np}{\left(1+\frac 1p\right)^n}\;,$$

since the remaining product converges more quickly. (Also it looks more like something that might have a closed form.)

share|improve this answer
    
That looks sound. (Minor correction: not more than one of the $ n $ numbers.) Thanks for the response. –  anon Jul 7 '11 at 10:37
    
@anon: Thanks, corrected. –  joriki Jul 7 '11 at 10:45
1  
$p_3$ is the "Strongly carefree constant" $\prod_p \left(1 - \frac{3}{p^2} + \frac{2}{p^3}\right)$. See mathworld.wolfram.com/CarefreeCouple.html and references there. –  Robert Israel Jul 7 '11 at 17:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.