2
$\begingroup$

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.

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

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)$.
$\endgroup$

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.