# In a given sequence of consecutive integers, finding the count of integers with a least prime factor greater than $p$

If a number $x$ has a least prime factor of $3$, then it is necessarily of the form $6y+3$ and the next number with a least prime factor of $3$ is $6y+9$. Between these two numbers there are always $2$ numbers $6y+5$ and $6y+7$ where the least prime factor is greater than $3$.

If a number $x$ has a least prime factor of $5$, then it is either of the form $30y+5$ or $30y+25$. Between these two numbers there are always $2$ numbers whose least prime factor is greater than $5$. Between $30y+5$ and $30y+25$, there are $6$ and between $30y+25$ and $30y+35$, there are $2$.

I can repeat this same type of analysis for all the primes. Between any two numbers who least prime factor is $7$, there are at least $2$ numbers with a least prime factor greater than $7$ and if there are no other numbers with a least prime factor of $7$ in between, there are at most $11$ of these type of numbers.

If there are two numbers $x,y$ with the same least prime factor $p$ where $y > x$ and where there is no number in between has a least prime factor $p$, is there any known equation for determining the minimum count of integers in between with a least prime factor greater than $p$ and the maximum count of integers in between with a least prime factor greater than $p$?

Does it continue to increase for all primes so that for $p \ge 7$, the minimum is greater or equal to $2$ and the maximum is greater or equal to $11$? Are there any well known results along these lines?

I am especially interested in estimates of least prime factors between $x$ and $y$ where $y > x$, $lpf(x)=lpf(y)$ and there is no number $z$ such that $x < z < y$ and $lpf(z)=lpf(x)$.

Edit: I fixed a mistake pointed out by Peter Kosinar.

• The case $p=7$ seems to have minimum of $2$ instead of $3$: Consider the interval $[203,217]$. – Peter Košinár Dec 29 '13 at 18:11
• Thanks! I fixed the mistake. – Larry Freeman Dec 30 '13 at 7:28

Let's start by proving something about the "minimum" for prime $p>2$.

Set $m$ equal to product of all primes smaller than $p$ and consider integers $$x=(m-1)p=mp-p\\y=(m+1)p=mp+p$$ They both have $\mathrm{lpf}(x)=\mathrm{lpf}(y)=p$. Now, if you take any integer $z$ between them, the absolute value of the difference $d=|z-mp|$ will be smaller than $p$. There are three cases to consider:

• $d=0$, which means $z=mp$ and $\mathrm{lpf}(z)=2<p$ due to construction of $m$, or
• $d=1$, which implies $z=mp\pm 1$ and since the product is divisible by all primes up to $p$, its least prime factor certainly exceeds $p$, or
• $1<d<p$, which implies $d$ has some prime divisor $q<p$. But since $m$ is divisible by all primes smaller than $p$, so is $z$ and thus $\mathrm{lpf}(z)\leq q<p$.

Thus, there are exactly two numbers whose $\mathrm{lpf}$ exceeds $p$ in this interval, which implies the "minimum" cannot exceed $2$.

We can also derive an easy observation regarding the average count of such numbers. It's sufficient to look at the interval $[0,pm-1]$, since the pattern of divisibility by primes up to $p$ repeats with period $pm$:

• A number $k$ has $\mathrm{lpf}(k)=p$ if any only if it is multiple of $p$ and $(k/p)$ does not have any factor smaller than $p$ or, equivalently, if it is coprime to $m$.
• Thus, there are exactly $\phi(m)$ such numbers, since $0\leq (k/p)<m$ and there are $\phi(m)$ integers coprime to $m$ smaller than $m$.
• There are exactly $\phi(pm)=(p-1)\phi(m)$ numbers whose $\mathrm{lpf}$ exceeds $p$; since they must be coprime to $pm$.
• Therefore, the average number of "exceeding" integers in one interval is precisely $(p-1)$.