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?


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)}) $$

  • $\begingroup$ Thanks very much for your answer. Does this analysis suggest that the my analysis is incorrect unless $2^p$ is much smaller than $n-m$? Could you add details explaining what this says about the upper limit of how many $w$ are divisible by $p$. $\endgroup$ – Larry Freeman Apr 10 '17 at 23:13
  • $\begingroup$ @LarryFreeman Your upper bound simply says that $w \le \lfloor n/p \rfloor$ which is trivial. I wanted to show that using a sieve, you can get more subtle results. $\endgroup$ – reuns Apr 11 '17 at 15:04
  • $\begingroup$ Apologies. I'm unclear how it is trivial. It may be that I am missing something obvious. Let $R$ be the set of integers between $m$ and $m+n$ where lpf($x$) $\ge p$ so that $|R| = w$. How can we sure that no more than $\left\lfloor\frac{w}{p}\right\rfloor$ of elements in $R$ are divisible by. $p$. It seems to me I can find an example where this is not true: $m=90, n=30, p=7$, $R=\{91, 97, 101, 103, 107, 109, 113, 119\}$ and $w=8$ but there are more than $\left\lfloor\frac{8}{7}\right\rfloor$. Please let me know if I am misunderstanding your point. $\endgroup$ – Larry Freeman Apr 11 '17 at 15:49
  • $\begingroup$ @LarryFreeman : In $[m,m+n] $ there are at most $\lfloor n/p \rfloor+1$ numbers divisible by $p$. This is again trivial. $\endgroup$ – reuns Apr 11 '17 at 16:15
  • 1
    $\begingroup$ @LarryFreeman It is true because if $p | k$ and $lpf(k) \ne p$ then $pl | k$ with $l$ is a product of primes $< p$. The inclusion-exclusion principle does the rest (count those dividable by $p$, remove those dividable by $2p$ and $3p$, but we counted twice those dividable by $6p$, ...) $\endgroup$ – reuns Apr 11 '17 at 20:28

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.