More generally, for an integer $n \gt 1$, let $L(n)$ be the largest number $k$ so that there is an integer $m$ where each of the $k$ consecutive integers $m+1, \cdots, m+k$ has a prime factor in common with $n$. $L(n) \geq \omega(n)$, the number of distinct prime factors of $n$, and if the least prime factor $p$ of $n$ is not too small (say, $p \gt 1+ \omega(n))$, then we have $L(n) = \omega(n)$, courtesy of the Chinese Remainder Theorem.

This was observed by Jacobsthal in a 1961 paper. Erdos observed later that for most $n$, $L(n)$ was not much larger than $\omega(n)$ (for these $n$ with prime factors not too small, one would have $L(n) \lt \omega(n)\log(\omega(n)$), and later still upper bounds both implicit and explicit on $L(n)$ were obtained by Kanold, Stevens, Iwaniec, and others. The hope is that $L(n) \lt \omega(n)^{2-\epsilon}$ for all $n \gt 1$ with $\omega(n) \gt 1$, but at this writing we are at least a couple of $\log \omega(n)$ factors away from that.

The reason for this post is to provide an alternate interpretation of the question. Such a longest interval of consecutive integers not coprime to $n$ exists, with largest element less than $n-1$, and almost always with largest element less than $n/2 -1$. By arguments I have not yet found, this interval has (conjecturally) fewer than $(\omega (n))^3$ members. How close to zero is this interval?

Other than an upper bound of $n/2 +1$, not much is known. There is some interesting behaviour observed for some $n$ with $\omega(n)$ odd: you can add some of the maximal intervals in a weird way to get another maximal interval. (Try it yourself with n=385.) This leads to a proof that a maximal interval with the smallest positive members is below $n/3$, and suggests that for these and other $n$ one can find such a maximal interval below $n/\omega(n)$.

When $\omega(n)$ is even, this fails badly. For some numbers with four distinct prime factors, one does not have such an additive relationship among intervals, and there are some $n$ where all the maximal intervals cluster around $n/2$. It is unclear in general where to look for such a maximal interval, but starting near $n/2$ seems to be a better choice. (In the case $n$ is twice a prime, it is clear where to look for a maximal interval, as there is only one such in $(0,n).)$

For the posted choice of argument being a factorial, of course the first such interval is smaller than half of the corresponding primorial (when $n! \gt 6$), and one can look at large prime gaps to conjecture growth for larger primorials, but this is just part of the picture for this area of study.

Gerhard "Looks At These Things Differently" Paseman, 2019.01.15.

8more comments