# Probability that randomly chosen integers from a restricted set of natural numbers are coprime

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."

-
@ 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$. –  Nilotpal Sinha Jan 30 '13 at 7:42
@ Daniel: Thanks for bringing it up. I have tried to make the meaning of 'all natural numbers' clearer in the new edit. –  Nilotpal Sinha Jan 30 '13 at 7:45
Cool--I've removed my earlier comments. –  Daniel Litt 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.

-
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$. –  i707107 Feb 8 '13 at 1:52