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 and Smallest number which begins the maximal number of consecutive integers divisible by one of the first n prime numbers 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.

Now that it looks like I am close to the intent of the question, I will point in the direction of the answer.

I recommend checking out wheel sieving using an array of differences. Note that if you store differences between unmarked items, you save on space and add a little on time: to get the next candidate add the current difference to the current candidate. However, the sequence of differences is periodic, so you can save a lot of space and manage time more effectively by just doing the work needed in one period. Thus, instead of looking at

2 2 2 2 2 ...

4 2 4 2 4 2 ...

6 4 2 4 2 4 6 2 6 4 ...

you instead work with 2 then with 4 2 then with 6 4 2 4 2 4 6 2 and so on. I invite you to find the algorithm on your own. Crandall and Pomerance have an algorithmic prime number book which has pseudocode if you want a reference.

The relevance of the above is that you are looking for an array of differences where the first difference is q-1 and one of the differences is 2q. I am confident there is one where q is less than 97. Possibly q is 43. When you find it, you will have (be able to construct) an example as suggested above, and where the code you mentioned will fail to remove a composite number.

Gerhard "Yes, Jacobsthal's Function Is Related" Paseman, 2012.12.08