Counting integers in a consecutive sequence where least prime factor is greater than $3$.

93 Views Asked by At

I am attempting to count the number of integers with a least prime factor greater than $3$ in a sequence of consecutive integers.

For example, if I count the number of integers in $10,11,12,13,14,15$, the number is $2$ since $\{11,13\}$ have a least prime factor greater than $3$.

I feel that my argument is too long and can be improved. I would appreciate any suggestions for making it more concise, more precise, or more standard.

Let $p_n > 3$ be the $n$th prime, $m>0$ be an integer.

Claim: $\left(\sum\limits_{m < x < m + p_n \text{ and } \text{lpf}(x) > 3} 1\right)\ge n-2$

Argument:

(1) If $m=1$, there are clearly $n$ primes between $1$ and $(1+p_n)$ and $n-2$ are greater than $3$.

(2) For $m=6i+1$, this is clearly true based on (1) since for every $1 < x < (1+p_n)$ where lpf$(x) > 3$, $6i+1 < x+6i < (6i+1 + p_n)$ and lpf$(6i+x) > 3$

(3) For $m=6i+2, m=6i+3, m=6i+4$, it is true from (2) since $6i+2, 6i+3, 6i+4$ all have least prime factor $\le 3$. So that there are $n-2$ integers where lpf$(x+6i) > 3$, $6i+4 < x + 6i < (6i+1+p_n)$

(4) For $m=6i$, this is true for $n-3$ integers based $6i+1 < x+6i < (6i+p_n)$ and it is true for $n-2$ integers since $6i < 6i+1$ and lpf($6i+1) > 3$

(5) For $m=6i+5$, there are $n-3$ integers between $6i+5 < x+6i < (6i+p_n+1)$. If $p_n = 6j+1$, then lpf$(6i+p_n+4) > 3$. If $p_n=6j+5$, then lpf$(6i+p_n+2) > 3$. Either way, there are $n-2$ integers $6i+5 < x+6i < (6i+p_n+5)$