Longest sequence of consecutive integers which are not coprime with $n!$

Question

For any integer $n$, the factorial $n!$ is the product of all positive integers up to and including $n$. Then in the sequence

$$n!+2,n!+3,... ,n!+n$$

the first term is divisible by $2$, the second term is divisible by $3$, and so on. Thus, this is a sequence of $(n − 1)$ consecutive composite integers, which definitely not coprime with $n!$.

Question: Is this the longest sequence of consecutive integers which are not coprime with $n!$ (less than $n!$)?

On the other words, is $(n-1)$ is the length of the longest sequence of consecutive integers which less than $n$ factorial and not coprime with it? Or can we find longer?

Answer 1

It is apparent that $n!\pm k$ are composite and not coprime to $n!$ for $2\le k\le n$. Of course, $n!$ is itself composite and not coprime to itself. Longer runs of composite numbers (up to lengths roughly $2n$) can occur when one or especially both of $n! \pm 1$ happen to be composite.

$n! \pm 1$ are both composite for $n=5,8,9,10,13\dots$; however, $n! \pm 1$ whether or not composite will be relatively prime to $n!$ and such longer runs do not satisfy the requirement in the original question of containing only "not coprime" numbers. For example, the run $114,\dots,126$ identified in a previous answer surrounds $5!=120$ but includes $5!-1=7\cdot 17$ and $5!+1=11^2$. Each of $7,11,17$ is relatively prime to $5!$

By careful choice, examples of $n$ can be manufactured where $n!\pm k$ continues to afford composite, not coprime, values for consecutive integers even when $k>n$. For example, if $n$ is odd, then $n!\pm (n+1)$ will be divisible by $2$ (as will every value of $k=n+2i+1$). We can further identify values of $n$ such that $n$ is odd and $3\mid (n+2)$. The Chinese Remainder Theorem says this process can be repeated to find values of $n$ that meet those requirements and further meet $5\mid (n+4)$, $7\mid (n+6)$, etc. to extend the runs of consecutive numbers not coprime to $n!$ by a few with each step. An example of this kind of extension was given in a previous answer.

What is apparent, however, is that every time we look to make the run of "not coprime" numbers a few longer, the values of $n$ and hence $n!$ grow very rapidly, quickly outstripping our ability to calculate by hand or even with simple calculators.

Answer 2

Starting with $x=7$ and noting that $8,9,10$ all have factors in common with $7!$, we quickly get the counterexample $$n=7\quad \&\quad \{7!-2,\;7!-3,\;7!-4,\;7!-5,\;7!-6,\;7!-7,\;7!-8,\;7!-9,\;7!-10\}$$

which is a string of length $9$ (and all terms are less than $7!$)

Answer 3

In general I think it's hard to determine to find the longest possible sequence of consecutive values coprime to $n!$ (equivalently the longest possible sequence of consecutive values all divisible by a prime less than or equal to $n$).

The answer given by lulu can be used to generate a sequence of length $p-2$, where $p$ is the least prime greater than $n$. But this bound is not sharp.

As an example, for the value $n=12$ the longest such sequence is of length 13. An example is given by the range from 114 to 126.

To see that no sequence of length 14 is possible, note that in any sequence of fourteen values there are exactly 7 even values, at most 1 odd value divisible by each of 7 and 11, at most 2 odd values divisible by 5, and at most 3 odd values divisible by 3. This adds up to 14, so such a sequence is only possible if no odd values are divisible by more than one of 3,5,7,11. However, the existence of 3 odd values divisible by 3 requires both the largest and smallest odd values to be divisible by 3, and the existence of 2 odd values divisible by 5 requires either the largest or smallest odd value to be divisible by 5.

I don't see a general method to prove such a sharp bound for arbitrary $n$ that avoids getting in the weeds to this extent, so I think there might not be a nice answer in general.