We know that the probability $P(k)$ of $k$ randomly chosen integers $(k \ge 2)$ from the set of natural number are coprime is

$$ P(k) = \frac{1}{\zeta(k)}. $$

I am looking at a special case of this problem. Let $S_n$ be the set of all natural numbers which do not have a prime factor greater than $n$-th prime (i.e $S_n$ is the set of natural numbers that can be formed using only the first $n$ prime numbers). What is the probability $P(k, S_n)$ that $k$ randomly chosen integers $(k \ge 2)$ from the set $S_n$ are coprime?

I do not know the answer but I think it could be in a parametric form involving $n$ such that in the trivial case when $n\to \infty$, $P(k, S_{\infty}) = P(k) = 1/\zeta(k)$.

Edit: Explained the meaning of "all natural numbers."

  • $\begingroup$ @ Daniel: Let me explain with an example. Say $n=2$, i.e. we are considering the first two prime numbers. So the set of all natural numbers that can be formed using only the first two primes is the set {2, 3, 4, 6, 8, 9, 12, ...} i.e. every natural numbers of the form $2{a}.3{b}$ where $a≥0$ and $b \ge 0$. $\endgroup$ Jan 30 '13 at 7:42
  • $\begingroup$ @ Daniel: Thanks for bringing it up. I have tried to make the meaning of 'all natural numbers' clearer in the new edit. $\endgroup$ Jan 30 '13 at 7:45
  • $\begingroup$ Cool--I've removed my earlier comments. $\endgroup$ Jan 30 '13 at 8:08

First of all, note that there is no canonical notion of equidistribution on a countable set like the integers.

When asking for the probability that $k$ 'randomly chosen' integers are coprime, it is more-or-less intuitively clear what is meant by 'randomly chosen'. This is basically because the density of integers divisible by a given prime $p$ is (up to 'differences from rounding') the same in any interval $\{1, \dots, n\}$, namely $1/p$.

In your question this is not the case: for example in $S_4 \cap \{1, \dots, 10\}$, 5 of 10 numbers (= 50 percent) are even, while in $S_4 \cap \{1, \dots, 10^6\}$, 1070 of 1273 integers are even (which is about 84 percent) and in $S_4 \cap \{1, \dots, 10^{30}\}$, already 445064 of 462692 are even, which is about 96 percent.

So in order to make your question well-defined you need to be explicit about what you mean by 'randomly chosen'.


A reasonable thing to do would be to look at the number of pairs in $S_k \cap \{1 \cdots N\}$ which are relatively prime. For fixed $k$ this would go to zero and indeed the probability would go to $1$ that a randomly selected element is not relatively prime to anything else in the set (other than $1$ of course).

Looking further at the set $S_4 \cap \{2..10^{30}\}$ we can also say that over $78\%$ of the members are less than $10^{28}$ (So in the bottom $1\%$ sizewise) and that over $73\%$ are not relatively prime to anything else (i.e. divide by $2,3,5$ and $7$). The number of relatively prime pairs is $0.013\%.$

Perhaps looking at integers $m$ with all prime factors less than $m^{2/3}$ or something like that would be interesting but I do not have a feel for what the right question would be.

  • 1
    $\begingroup$ On the last statement, there are some results. $\psi(x,y)$ denotes the number of positive integers $\leq x$ such that all of their prime factors are $\leq y$. Then for $u\geq 0$, $\psi(x,x^{1/u})=\rho(u)x+O(x/\log x)$. where $\rho(u)$ is called Dickman's function. In case $1\leq u\leq 2$, it is just equal to $1-\log u$. $\endgroup$ Feb 8 '13 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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