Sieve of Erathostenes: removing consecutive items

Question

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 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).

Answer 1

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.

Answer 2

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

Answer 3

This question is answered in the paper Paul Pritchard, Some negative results concerning prime number generators, Comm. ACM, vol. 27, no. 1, Jan. 1984, pp.53-57 .

The paper notes (at the start of p.54) that "Misra's conjecture can be given a familiar setting: it amounts to the claim that in no pass of Eratosthenes' sieve are successive remaining numbers removed."

The paper provides a mathematical disproof, and gives explicit composite numbers that constitute a counterexample. It uses the notion of wheels, as suggested in another comment.

Answer 4

Let $q$ be the next prime after $p$. The fact that primes exist between $p$ and $2p$ implies that $a-b$ must be less then $2$. This reduces the problem to finding a number $a$ and prime $p$ such that $ap+1, ap+2 \ldots ap+p-1$ all have prime factors less then $p$ while $a$ has only prime factor greater then $p$. This is not a complete solution, but is a step forward.