# Counting the number of integers with their least prime factor greater than $x$ between $ax$ and $ax+x$

Let:

• $$x \ge 2, a \ge 1$$ be integers.
• $$x\#$$ be the primorial for $$x$$
• $$\mu(i)$$ be the möbius function.
• $$\text{lpf}(x)$$ be the least prime factor of $$x$$.
• $$p_k$$ be the $$k$$th prime which is the highest prime less than or equal to $$x$$
• $$r(m,d)$$ be the remainder when $$m$$ is divided by $$d$$

It follows that the count of $$i$$ such that $$ax < i \le ax+x$$ and $$\text{lpf}(i) > x$$ is:

$$\sum_{i|p_k\#}\left(\left\lfloor\frac{ax+x}{i}\right\rfloor - \left\lfloor\frac{ax}{i}\right\rfloor\right)\mu(i)$$

My question is whether I am correct that this value can be restated as:

$$\prod_{j=1}^k\left(\frac{p_j-1}{p_j}\right)x - \sum_{i|p_k\#}\left(\frac{r(ax+x,i)-r(ax,i)}{i}\right)\mu(i)$$

which implies that:

$$\prod_{j=1}^k\left(\frac{p_j-1}{p_j}\right)x \ge \sum_{i|p_k\#}\left(\frac{r(ax+x,i) - r(ax,i)}{i}\right)\mu(i)$$

Here is my reasoning:

$$\sum\limits_{i|p_k\#}\left(\left\lfloor\frac{ax+x}{i}\right\rfloor - \left\lfloor\frac{ax}{i}\right\rfloor\right)\mu(i) = \sum\limits_{i|p_k\#}\left[\left(\frac{ax+x}{i}-\frac{r(ax+x,i)}{i}\right) - \left(\frac{ax}{i}-\frac{r(ax,i)}{i}\right)\right]\mu(i)$$

$$=\sum\limits_{i|p_k\#}\left(\frac{ax+x}{i}-\frac{ax}{i}\right)\mu(i) - \sum\limits_{i|p_k\#}\left(\frac{r(ax+x,i)}{i}-\frac{r(ax,i)}{i}\right)\mu(i)$$

$$=\sum\limits_{i|p_k\#}\left(\frac{x}{i}\right)\mu(i) - \sum\limits_{i|p_k\#}\left(\frac{r(ax+x,i)-r(ax,i)}{i}\right)\mu(i)$$

$$=\prod\limits_{j=1}^k\left(\frac{p_j-1}{p_j}\right)x - \sum\limits_{i|p_k\#}\left(\frac{r(ax+x,i)-r(ax,i)}{i}\right)\mu(i)$$

Did I make a mistake?

## 2 Answers

As far as I can tell, everything is correct. However, I do have a few comments about my work to verify some of your statements.

First, you wrote

It follows that the count of $$i$$ such that $$ax < i \le ax+x$$ and $$\text{lpf}(i) > x$$ is:

$$\sum_{i|p_k\#}\left(\left\lfloor\frac{ax+x}{i}\right\rfloor - \left\lfloor\frac{ax}{i}\right\rfloor\right)\mu(i)$$

However, you don't specify how you can state "It follows ...". I found you asked at A question about the Mobius Function, where Terry Tao answered. He explains how to use the Möbius inversion formula along with the function

$$F_n(x) := \sum_{i|n} \lfloor \frac{x}{i} \rfloor \mu(i)$$

In particular, he stated

Indeed, the quantity $$F_{p_k\#}(x)$$ (that is, the number of natural numbers up to x that have no prime factor less than or equal to $$p_k$$) is more commonly denoted $$\pi(x,p_k)$$ in the analytic number theory literature.

As such, $$F_{p_k\#}(ax + x) - F_{p_k\#}(ax)$$, which is what your expression is, gives what you state that it does. Possibly due to number theory not being my area of expertise, I wasn't aware of this & had some trouble determining it. Therefore, I don't think that you should assume it's obvious to readers here, especially as you're using the "elementary-number-theory" tag for your question, so the people reading it would encompass a fairly wide range of knowledge & expertise. In this case, I suggest you should have just included a link to that post. If you had, it would've saved me quite a bit of time & effort in trying to determine & verify your statement.

I also note you implicitly used the Möbius inversion again to get to your last line. In particular, it states in Möbius Function that

$$\frac{\phi(n)}{n} = \sum_{d \mid n}\frac{\mu(d)}{d}$$

Using $$n = p_k\#$$, along with the definition at Euler's totient function of

$$\varphi(n)=n\prod_{p\mid n}\left(1-{\frac {1}{p}}\right)$$

gives that

$$\prod\limits_{j=1}^k\left(\frac{p_j-1}{p_j}\right) = \sum\limits_{i|p_k\#}\left(\frac{\mu(i)}{i}\right)$$

This, I suspect, is more generally widely known than your earlier statement, but I suggest it still would be a good idea to briefly mention what you're using.

In general, keep in mind that, even if the person reading your text is familiar with the proof of what you're using in a statement, they may have trouble recognizing it if they haven't used or thought about it for a long time. As such, it could take them longer, & cause them more difficultly, to understand what you're stating than if you had given more details. Thus, unless it is something quite basic for your expected audience, I believe it's better to offer at least some minimal explanation.

• Thanks very much for your comments. I appreciate your analysis of my question! I've been using many of these ideas so often that I forget that they require details explaining why they are true. :-) – Larry Freeman Apr 20 at 5:45
• @LarryFreeman You are welcome. I, too, quite often have to keep in mind that what might seem "obvious" to me is not necessarily so to somebody else. – John Omielan Apr 20 at 6:07

http://mathworld.wolfram.com/LegendresFormula.html

where $$\phi(x,a)-1$$ counts the number of integers less than $$x$$ with their least prime factor greater than $$p_a$$

With your $$a$$ and $$x$$ notations it would give:

$$\phi(ax+x,\pi(x))-\phi(ax,\pi(x))$$

• Thanks for the reference. I had not known that this line of reasoning had come from Legendre. :-) – Larry Freeman Apr 20 at 6:43