Are coprimes to the set of primes less than the $i^{th}$ prime always between one multiple of $p_i$?

Question

I am not deeply familiar with mathematics, but I've run into an interesting question while programming that I would appreciate some help with. I'll provide context on the programming side of things to help clarify my question in case my description is lacking, but I want to emphasize that I'm interested in the mathematics part of this, and do not need help with the programming problem.

I've been working on an implementation of https://swtch.com/~rsc/thread/, where in short I implement the sieve of Eratosthenes in an interesting way using the following pseudocode:

p = get a number from left neighbor process

print p

loop:
    n = get a number from left neighbor process

    if (p does not divide n)
        send n to right neighbor process

Essentially, each process consumes a prime number $p$ and then culls all input numbers that are not coprime to $p$. Since each process to the left will only produce coprimes, each successive process is getting a stream of numbers that are coprime to all of the primes less than the process's prime $p$.

Here is a link to an image demonstrating the flow of numbers. (I would have embedded this if I had enough reputation.)

I've discussed this with a friend, and we figured that instead of using division, it would likely be faster to use addition - that is, instead of dividing by $p$ every time, you could keep track of a current multiple $m$ of $p$, and have something like the following:

p = get a number from left neighbor process
mp = p

print p

loop:
    n = get a number from left neighbor process

    if (mp < n)
        mp += p

    if mp == n
        continue

    send n to right neighbor process

I've tested this with a small number of primes and this works. My question is: is this valid for all primes? That is, for the $i^{th}$ prime $p_i$, will the sequence of coprimes to the set $S_i = \{p_1, p_2, ..., p_{i-1}\}$ ever produce a gap that is larger than $2p_i$?

Or does the function need to handle the possibility that $n$ could be greater than or equal to $mp+2p$ with a loop, like:

p = get a number from left neighbor process
mp = p

print p

loop:
    n = get a number from left neighbor process

    for (; mp < n; mp += p);

    if mp == n
        continue

    send n to right neighbor process

I've done some searching here and elsewhere, but I'm having a hard time phrasing the question in the first place due to my inexperience with mathematics. Intuitively I feel like it is true, but I also am not equipped to prove it.

I believe that "Range of numbers not divisible by 2 or 3 or 5", "The number of numbers not divisible by 2,3,5,7 or 11 between multiples of 2310", and "Is that true that all the prime numbers are of the form 6m±1?" are likely related, but it's not clear to me how to apply that to my particular question.

Answer 1

I was able to find a proof by counterexample for $p = 13$, since:

• 9113 and 9127 are adjacent coprimes to the set $\{2, 3, 5, 7, 11\}$.
• 9113 is a multiple of 13 ($13 × 701 = 9113$).
• $9113 + 13 = 9126$, and $9126 < 9127$.

So in the code above, a single increment of $mp$ by $p$ when $p = 13$ would not suffice for the sequence of $9113, 9127$.

I think this could have been proven without running the program by looking at the Jacobsthal function applied to the product of the first n primes, A048670, since:

• any process for the $i^{th}$ prime $p_i$ would only see numbers coprime to the product of ${2 × 3 × ... × p_{i-1}}$
• $A048670(i-1)$ gives the maximal gap between coprimes to the product of ${2 × 3 × ... × p_{i-1}}$

and when $i = 6$,

• $p_6 = 13$
• $A048670(6-1) = 14$

So the process for 13 would, on some basis, see a gap of 14 in the coprimes it read from the processes to its left, and eventually that gap would happen directly after a multiple of 13, leaving it unable to cross the gap with a single increment of 13. This appears to first happen between 9113 and 9127.