I am reading through an AMS.org article on prime counting.
- Let $\Phi(x,b)$ be the number of integers $i$ where $1 \le i \le x$ and $\gcd(i,p_b\#)=1$ where $p_b$ is the $b$th prime and $p_b\#$ is the primorial for $p_b$
- Let $\Phi(x,0) = x$
Based on these two definitions, $\Phi(x,b)$ has the following two properties:
- $\Phi(u,0) = \left\lfloor{u}\right\rfloor$
- $\Phi(x,b) = \Phi(x,b-1) - \Phi(\frac{x}{p_b},b-1)$
I am clear on how these properties derive from the definitions.
The part that I am not clear on is the generalization to the following form:
$$\Phi(x,b) = \sum_{1 \le n \le x \text{ and } p^+(n) \le y }\mu(n)\left\lfloor\frac{x}{n}\right\rfloor$$
where $\mu(n)$ is the möbius function and $p^+(n)$ is the greatest prime factor of $n$.
Here are my questions:
- I am not clear where $y$ is coming in or why $p^+(n)$ is being used.
- I am not clear how the two equations above generalize to the möbius function.
- I am not clear why the equation with the möbius function works.
If someone knows a reference that explains this in more detail, that would be very helpful.
Edit: I've made some progress based on the answer to this question.
Since $\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor = \left\lfloor\frac{a}{bc}\right\rfloor$, I am now clear on how the möbius function fits in.
I am still not clear on where $y$ is arbitrarily chosen between $x^{\frac{1}{3}}$ and $x^{\frac{1}{2}}$.
I am now clear on $p^+(n) \le y$ since if $p^+(n) > y$, it follows that there is another prime less than $y$. So, we are doing this to avoid double counting these integers.