Let $m \ge 2$ be an integer.

Let $p_n$ be the $n$th prime so that $p_1 = 2, p_2 = 3,$ etc.

Let $p_n\#$ be the primorial for $p_n$.

Let $\gcd(a,b)$ be the greatest common divisor for $a$ and $b$.

Let $f(m,p_n) =$ the number of integers $x$ where $0 < x \le m$ and $\gcd(x,p_n\#)=1$

For example:

  • $f(10,2)=5$
  • $f(10,3)=3$

It seems to me that $f(m,p_n)$ can be estimated in the following way:

$$\left\lfloor\left(\prod\limits_{p_i \le p_n}\frac{p_i-1}{p_i}\right)m\right\rfloor \le f(m,p_n) \le \left\lceil\left(\prod\limits_{p_i \le p_n}\frac{p_i-1}{p_i}\right)m\right\rceil$$

Here's my argument:

For any $m$:

  • at least $\left\lfloor\frac{m}{2}\right\rfloor$ are odd
  • at least $\left\lfloor\left(\frac{2}{3}\right)\left(\frac{m}{2}\right)\right\rfloor$ are odd and not divisible by $3$,
  • at least $\left\lfloor\left(\frac{4}{5}\right)\left(\frac{2}{3}\right)\left(\frac{m}{2}\right)\right\rfloor$ are odd, not divisible by $3$ and not divisible by $5$.
  • and so on.
  • at most $\left\lceil\frac{m}{2}\right\rceil$ are odd.
  • and so on in the same way.

Is my reasoning valid? If yes, what is the standard argument? If my reasoning is not valid, could you provide a counter example?


This is correct, you are basically applying inclusion-exclusion formula. There are at least two kind of generalizations of the problem you mentioned above:

  1. Given pairwise coprime positive integers $a_1,\ldots,a_k$, then the number of positive integers $n\le x$ coprime with each $a_i$ admits asymptotic density $$ \left(1-\frac{1}{a_1}\right)\cdots \left(1-\frac{1}{a_k}\right). $$

  2. Given positive integers $a_1,\ldots,a_k$, then the number of positive integers $n\le x$ not divisible by each $a_i$ admits asymptotic density $$ \ge \left(1-\frac{1}{a_1}\right)\cdots \left(1-\frac{1}{a_k}\right). $$ For a proof see here and a textbook exposition here.

  • $\begingroup$ Thanks very much for your explanation and providing references to the proof! :-) $\endgroup$ – Larry Freeman Jun 5 '17 at 8:19
  • $\begingroup$ Under what conditions will this not be true? It has been pointed out that the inequality fails for $f(10,7)$ which equals $1$ but $\left\lfloor\left(\prod\limits_{p \le 7}\frac{p-1}{p}\right)10\right\rfloor = 2$ $\endgroup$ – Larry Freeman Jun 13 '17 at 6:55
  • $\begingroup$ @LarryFreeman the value $\prod_i \left(1-\frac{1}{a_i}\right)$ expresses the (natural) asymptotic density of the set of integers $n$ with the property of not being divisible by any $a_i$. Of course, the problem is periodic modulo $\mathrm{lcm}(a_1,\ldots,a_k)$. Therefore, you could say that $f(n,p_k\#)=\lfloor n/p_k\#\rfloor \prod_{i=1}^k ((p_i-1)/p_i)+\mathrm{error}$, with $\mathrm{error} \in \{0,1,\ldots,\varphi(p_k\#)-1\}$ (here $\varphi$ is the Euler's function). $\endgroup$ – Paolo Leonetti Jun 13 '17 at 15:22
  • $\begingroup$ Thanks very much for the clarification! That makes sense. $\endgroup$ – Larry Freeman Jun 13 '17 at 15:27

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.