1
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
12
  • $\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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 20:28

You must log in to answer this question.

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