Counting integers in a sequence with a least prime factor = $p$

110 Views Asked by At

Let $p > 2$ be a prime. It is very easy to count the integers in a sequence that are divisible by $p$.

Let $m \ge 0, n > 0$ be integers. The count of $x$ where $m < x \le (m+n)$ and $p | x$ is at most $1 + \left\lfloor\frac{n}{p}\right\rfloor$.

For example, if $m=6, n=8, p=7$, there are $2$ integers: $6 < \{ 7, 14\} \le 14$.

Let us assume that in the sequence described by $m,n$, there are $w$ integers where $\text{lpf}(x) \ge p$ where lpf is the least prime factor.

It seems to me that the most $1 + \left\lfloor\frac{n-p}{p}\right\rfloor$ of the $w$ that are divisible by $p$ so that this is an upper bound on the count of integers where $\text{lpf}(x) = p$.

The reason for $-p$ is that we can assume that if there are $2$ or more in sequence, at least one can be ignored since it would be divisible by $2$ and would not be included in $w$.

Is there a flaw in my thinking? Is there a better upper bound?

1

There are 1 best solutions below

12
On BEST ANSWER

By sieving I find $$\displaystyle w =\sum_{l\in A_{p}} \mu(l)\left(\left\lfloor \frac{n}{pl} \right\rfloor-\left\lfloor \frac{m-1}{pl} \right\rfloor\right)$$ where $\ \mu\ $ is the Möbius function and $\ A_{p}\ $ are the ( squarefree ) integers whose largest prime factor is $< p$.

So if $2^p$ is much smaller than $n-m$ : $$\displaystyle w =\sum_{l\in A_{p}} \mu(l) \frac{n-m+1}{pl}+ \mathcal{O}(2|A_p|)= \frac{n-m+1}{p}\prod_{q \text{ prime}, q < p} \left(1-\frac{1}{q}\right)+\mathcal{O}(2^{\pi(p)}) $$