## Sieve of Erathostenes: removing consecutive items

This question comes from http://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 http://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).

-
Since you have to remove the multiples of a prime, the problem to me seems to be removing a prime before it is recognized as such. If you remove composites early or late, but before you need them gone, the bug in timing does not matter. However, I do not understand what the bug is or what is meant by consecutive in this context; I would think 25 and 26 are consecutive, not 25 and 35. Gerhard "Ask Me About Buggy Sieves" Paseman, 2012.12.08 – Gerhard Paseman Dec 8 at 20:58
Having checked the ppro=r!m source, I think the question you want is the following: Is there a prime q and numbers n and n+kq such that the least prime factor of L(n) and L(n+kq) is q and every integer m in between has L(m) less than q?. I think so, and that the prime q is at least 23 (maybe it is 43), and n is certainly larger than 10^7. Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2012.12.08 – Gerhard Paseman Dec 8 at 21:20
Voting to close after noting that I'm not the only one who can't figure out what's being asked (in particular, what "consecutive" means, or what was intended in its place). – Steven Landsburg Dec 8 at 22:05
"Consecutive" means two numbers that are in the list so far, with no number in-between being in the list. Maybe I should try to rephrase the question in a purely mathematical way if such an algorithmic formulation doesn't work. – Armin Rigo Dec 8 at 22:20
A related question: mathoverflow.net/questions/49400/… . Aaron does not quite answer your question, but comes close. Also, if you study the wheel sieve, you may be able to predict where the desired gap will occur without computing the full sieve. Gerhard "Ask Me About System Design" Paseman, 2012.12.08 – Gerhard Paseman Dec 9 at 3:58

## 3 Answers

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{n^2}{2\ln{n}} .$) $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 black, 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.

-
Thanks! It still seems to me that there must be other solutions for $p<73$, but it is still definitely an answer to my question. – Armin Rigo Dec 9 at 13:46
To answer the original question from stackoverflow, we'd need for example an $s'$ such that $s' + 2\dot 73$ equals $73$ times a prime number (because the $s + 2\dot 73$ given here would still be removed later when we are at the step $p=1033$). There are some in the arithmetic sequence that starts at the given $s$ with step $2\dot 3\dot 5\dot ... \dot 73$. In fact the next element in this sequence is already $73$ times a prime number. – Armin Rigo Dec 9 at 14:43
(Sorry, misplaced the dots. I meant $2 x 73$ and $2 x 3 x 5 x ... x 73$.) – Armin Rigo Dec 9 at 14:45
I am a little surprised at the first prime p = 67. (This is because j(43#)> 86.) I would expect 43 or 47 to be the first prime. I can believe that the smallest example is associated with p=67, however. Gerhard "Ask Me About Large Examples" Paseman, 2012.12.09 – Gerhard Paseman Dec 9 at 20:24
I love this: "The universe is infinite and our horizon is small"! – Joseph O'Rourke Dec 10 at 0:25
show 5 more comments

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.

-
 I believe that many reasonable interpretations of your suggestion are steps in the wrong direction. In particular I think a and b are both odd. Gerhard "Not Ready For Unreasonable Interpretations" Paseman, 2012.12.08 – Gerhard Paseman Dec 8 at 23:18 Well, if that is the case then $(a-b)p>q$ because there is a prime between $2p$ and $p$. And so one number in the range $ap$ to $bp$ must be divisible by $q$. – Watson Ladd Dec 9 at 1:37 Yes, there is some $n$ divisible by $q$, but it doesn't imply that $L(n) > p$. – Armin Rigo Dec 9 at 1:59 OK. Even if it is divisible by q, so what? That multiple of q may have least prime something other than q. Gerhard "Ask Me About System Design" Paseman, 2012.12.08 – Gerhard Paseman Dec 9 at 2:17 That is true. I should think harder about what $L(n)$ means, and hopefully come up with something useful. – Watson Ladd Dec 9 at 2:18

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

-
 Thanks for the tips! I already had algorithms that compute the maximum number in such sequences, but yours is indeed less memory-hungry. But it still hits memory limits: from q=31 onward the sequence is longer than 840 million items (and of course growing very fast). I estimated the maximum value in the first ~600 million items for q up to 227 and all of them are lower than 2q, but obviously it might be because I'm only looking at an ever-smaller fraction of the sequence when q grows. – Armin Rigo Dec 9 at 0:10 Found a way to compute the maximum of the whole list with bounded memory. Still running to algorithm, but so far I have: p=29, max=40; p=31, max=46; p=37, max=58?; p=41, max=66??. Based on naive extrapolation it seems that $max>=2p$ will occur between $p=43$ and $p=53$. In any case it is clear that it does eventually occur. – Armin Rigo Dec 9 at 13:34