MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
@ 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'.

share|cite|improve this answer

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.

share|cite|improve this answer
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

Your Answer


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.