# Sequence of consecutive integers containing a relatively prime number.

Is there a published result that says the following?

Let $p$ be an prime number. Then for all integer $n>p$ there is at least one number in the consecutive sequence $2n,2n+1,2n+2,\ldots,2n+2p-1$ that is relatively prime to all prime numbers less than or equal to $p$.

For example, if $p=5$ and $n=17$, the sequence $34,35,36,37,38,39,40,41,42,43$ has several numbers not divisible by $2,3,5$. Now this just needs to be true for any $n>p$ and any prime $p$.

I have already asked my colleague who received his Ph.D. in Number Theory. He suggested I pose it to a wider audience, hence why I'm here. Any suggestions on results would be greatly appreciated.

• I'd say we know something a bit stronger which is, the sequence of prime numbers contains arithmetic subsequences of arbitrary length which is due to Green and Tao (2004). – Raito Nov 12 '17 at 23:26
• @Raito you are misunderstanding the question due to the ambiguous use of the word "any": sometimes it means some ("does this equation have any solution?") and sometimes it means all (for any $\varepsilon > 0\ldots$). When writing "for any integer $n > p$" I believe the intention is "for all integers $n > p$," in which case the Green--Tao theorem doesn't help. – KCd Nov 13 '17 at 2:20
• @KCd is right. I apologize for ambiguous use of "any". I have edited it to make it more clear. – John Asplund Nov 13 '17 at 12:18

The conjecture is false.

Let $p_1, p_2, p_3, \dots$ be the primes. Define the primorial Jacobsthal function $h(k)$ to be the smallest length $\ell$ such that every consecutive sequence of integers of length $\ell$ contains a number relatively prime to $p_1, \dots p_k$. Your conjecture is equivalent to the assertion that $h(k) \le 2 p_k$.

(The condition is invariant upon adding or subtracting multiples of $P = \prod_{i=1}^k p_i$, so the condition that $n > p$ is irrelevant, and for fixed $p$ the conjecture can be verified by a finite calculation; it suffices to examine consecutive sequences of integers between $0$ and $P - 1$ inclusive.)

According to the table of values of $h(k)$ in the linked paper we have

$$p_{14} = 43, h(14) = 90 > 86$$

so there is a consecutive sequence of $89$ integers none of which is relatively prime to the primes up to $43$. This is the smallest counterexample.

You can show that $h(k) \ge 2p_{k-1}$ by constructing a consecutive sequence of integers of length $2p_{k-1} - 1$ none of which is relatively prime to $p_1, \dots p_k$. This can be done by considering the integers $n - a, n - a + 1, \dots n + a - 1, n + a$ where $n$ is a solution to the system of congruences

$$n \equiv 0 \bmod p_1 \dots p_{k-2}$$ $$n-1 \equiv 0 \bmod p_{k-1}$$ $$n+1 \equiv 0 \bmod p_k$$

and $a = p_{k-1} - 1$. This construction is actually best possible for $p_k \le 19$; for example when $p_k = 19$ it produces the sequence $60044, \dots 60076$. It first stops being best possible when $p_k = 23$, where this construction gives a sequence of length $37$ but the longest sequence has length $39$ (namely $20332472, \dots 20332510$).

For completeness' sake here is the (very sloppy, I'm sure) Python script I used to test the conjecture; it allowed me to compute enough values of $h(k)$ that I could look it up on the OEIS, and looking at the longest sequences led me to the construction above. Note that it computes $h(k) - 1$, the length of the longest sequence of integers not relatively prime to $p_1, \dots p_k$.

from sympy import sieve
from math import gcd
from operator import mul
import functools as ft

def longest(p):
primes = list(sieve.primerange(1, p+1))
product = ft.reduce(mul, primes, 1)

biglist = list(range(0, primordial(p)))

def isrelprime(n):
for p in primes:
if gcd(n,p) != 1:

best = 0
bestlen = 0
curlen = 0
for i in biglist:
if not isrelprime(i):
curlen += 1
else:
curlen = 0
if curlen > bestlen:
best = i
bestlen = curlen

print("\nPrime : " + str(p))
print("Best : " + str(best))
print("Length : " + str(bestlen))

for i in range(0, bestlen):
print(str(best - i) + " has gcd " + str(gcd(best - i, product)))

primes = list(sieve.primerange(1, 20))
for p in primes:
longest(p)


And here's a little bit of extra code for computing the gcd of a particular sequence of consecutive integers with the product of the primes up to some prime.

def check(n, p, len):
primes = list(sieve.primerange(1, p+1))
product = ft.reduce(mul, primes, 1)
for i in range(0, len):
print(str(n - i) + " has gcd " + str(gcd(n - i, product)))

check(60076, 19, 33)
check(20332510, 23, 39)