This question comes from <https://stackoverflow.com/questions/13747873/why-does-this-prime-function-work>, where somebody wrote a standard Sieve of Erathostenes algorithm --- with a bug. However, the bug does not have any bad effect up to 1'000'000. At this point, it would be interesting to know if we can find either a proof or a counter-example.


The question is: let L(n) denote the smallest prime factor of n. Is there a prime number p and two integers b > a >= 2, with:


* L(ap) = L(bp) = p
* for any m such that ap < m < bp, L(m) < p.


The question and comments in [question in prime numbers](https://mathoverflow.net/questions/49400/question-in-prime-numbers) let us think that it might be false in general. However I don't really see how to draw that conclusion so far.


EDIT: reformulated the problem (now close to Gerhard Paseman's formulation).



Sieve of Erathostenes: removing consecutive items
There are more efficient ways to sieve, however the question as asked is interesting. I think that there will be a failure for $p=73$ at about $3.08 \times 10^{27}$. First a reformulation which I *think* is equivalent:



> 
> Choose an odd prime $p$ and color the integers (starting at $2$) according to least prime divisor: Color $n$ white, green or red according as the least prime divisor of $n$ is $\lt, =,$ or $ \gt p.$
> 
> 
> Q: Is it the case that , for every $p$, there is always at least one red integer between each green integer and the next?
> 
> 
> 


The colors relate to a simple idealized implementation of the Sieve of Erasthostenes on all integers greater than one. The white integers are already struck out by the time we get to the prime $p$. The green will be newly struck out using the prime $p$ and the red survive this step still unstruck.


The first green integer is $p$ itself and the next is $p^2.$ In between are a healthy number $m\_p$ of red integers, all of which are prime (one would expect $m\_p \approx \frac{p^2-2p}{2\ln{p}} .$) $p^3$ is also green. The green integers from $p^2$ up to $p^3$ are the $m\_p$ numbers $pq$ where $q$ is one of the primes just mentioned. The red numbers from $p^2$ up to $p^3$ are the many primes in this range along with the $m\_p(m\_p+1)/2$ products $qq'$ where $q \le q'.$ All this does not rule out there being two green integers much further out with no red number between them. The entire pattern of *white*, green and red has period $p$#, the product of the primes up to $p$ although that is quickly very huge. The next green number after $n$ is $n+2pj$ for some $j \ge 1.$ So the first question is "*can there be a run of at least $2p+1$ consecutive integers, all white and green?*" Here the OEIS items [Largest number of consecutive integers such that each is divisible by a prime <= the n-th prime](http://oeis.org/A058989) and [Smallest number which begins the maximal number of consecutive integers divisible by one of the first n prime numbers](http://oeis.org/A049300) along with their linked data tables become handy. ~~The first prime for which this can happen is $p=67$ where it happens for the $153$ integers starting at $s=7714600835154917969172.$ However we need a run which actually contains two green numbers and no red ones so the length alone is not enough. As it happens $s+61$ is a green so the next possible green number is $t=s+61+2\*67$ which already past the red number $s+154$ (and it turns out that $t$ is a multiple of $9\cdot17$).~~ 


But on further examination it seems that for $p=73$ we have two green numbers


$s=3084626641924131277081102913 =73 \cdot 483733 \cdot 169372703 \cdot 515739756619 $


$s+2\cdot 73=73 \cdot 1033 \cdot 40905285071067528770851$


and everything between them white because of the following minimal prime factors.


$73, 2, 5, 2, 3, 2, 19, 2, 41, 2, 3, 2, 5, 2, 17, 2, 3, 2, 53, $


$2, 29, 2, 3, 2, 31, 2, 7, 2, 3, 2, 13, 2, 5, 2, 3, 2, 23, 2, $


$11, 2, 3, 2, 5, 2, 19, 2, 3, 2, 17, 2, 47, 2, 3, 2, 7, 2, $


$13, 2, 3, 2, 11, 2, 5, 2, 3, 2, 37, 2, 7, 2, 3, 2, 5, 2,$


$ 43, 2, 3, 2, 29, 2, 67, 2, 3, 2, 71, 2, 31, 2, 3, 2, 41, $


$2, 5, 2, 3, 2, 7, 2, 61, 2, 3, 2, 5, 2, 11, 2, 3, 2, 13, 2,$


$ 7, 2, 3, 2, 59, 2, 17, 2, 3, 2, 19, 2, 5, 2, 3, 2, 11, 2, $


$23, 2, 3, 2, 5, 2, 13, 2, 3, 2, 7, 2, 37, 2, 3, 2, 47, 2, 73$


**updates** As @Gerhard points out, I was too hasty. I gap of $2p+1$ can not happen for $p=53,59,61$ nor for $p \le 41$ but does happen for $p=43,47.$ I leave the examination of those possible cases to someone else. The case I discuss for $p=67$ is the first attaining the maximal length for that $p$ of $153.$ But for all I know there is an earlier gap of length $135 \le \ell \le 152$ which has two green numbers with no red between them (or a later gap of some length $135 \le \ell \le 153$). Similarly for $p=73.$ As pointed out, The example given is likely not a counterexample for the original SE question. I almost feel as if a counterexample to that would require the larger number to be a power of $p$ or perhaps $p^aq^b$ with $ab$ large. I was only able to give the answer I did because the particular data was there and turned out to work.The universe is infinite and our horizon is small.


