3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Not following...the example you wrote does not contain any numbers smaller than $n!$, so what does that condition mean? Did you mean to write $n!-i$ instead of $n!+i$? $\endgroup$ – lulu Jan 10 at 2:06
  • $\begingroup$ Well if $n+1$ is composite then $n! + (n+1)$ isn't coprime either. (Although it will be if $n+1 $ is prime). $n! + k$ will only be coprime with $n!$ if all the prime factors of $k$ are larger than $n$. So the first term that isn't coprime will be $n! + p$ where $p$ is the first prime greater than $n$. $\endgroup$ – fleablood Jan 10 at 20:17
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is there any research showing the low bound to this question? Of course one can get as long as he wish which 'not coprime' with n!, but it will reach so big that out of calculation. What I am interesting is, the bound in range of <n!. $\endgroup$ – Ocean Yu Jan 14 at 5:49
4
$\begingroup$

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!$)

$\endgroup$
  • $\begingroup$ @RolfHoyer Yes. My guess, and it is just a guess, is that that is the answer, at least most of the time. $\endgroup$ – lulu Jan 10 at 2:11
  • $\begingroup$ thanks. that's correct. it is the counterexample. What is the longest one? Is 2n is the limited longest? $\endgroup$ – Ocean Yu Jan 10 at 2:13
  • $\begingroup$ @OceanYu Bertrand's postulate tells us that there is a prime between $n$ and $2n$ so my method can't get a string as long as $2n$, However, that doesn't prove that there isn't one. $\endgroup$ – lulu Jan 10 at 2:15
  • $\begingroup$ Looks like the longest sequence is not that easy to find in practice. for $n=12$ there are sequences of length 12. $\endgroup$ – Rolf Hoyer Jan 10 at 2:15
  • $\begingroup$ @RolfHoyer Ah, good. I think that example would be worth posting as a separate answer. $\endgroup$ – lulu Jan 10 at 2:16
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.