1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks very much for your explanation and providing references to the proof! :-) $\endgroup$ Commented Jun 5, 2017 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$ Commented Jun 13, 2017 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$ Commented Jun 13, 2017 at 15:22
  • $\begingroup$ Thanks very much for the clarification! That makes sense. $\endgroup$ Commented Jun 13, 2017 at 15:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .