4
$\begingroup$

Is there any research on getting upper bound of the maximal possible number of consecutive positive integers which are less than $n!$ and NOT coprime with $n!$?

Easy to see that lower bound $\ge n$, (example that $n= \text{odd prime}$). Does upper bound $<2n$ strictly?

Note that the discussion is in range of $<n!$.

$\endgroup$
13
  • $\begingroup$ This is mentioned in comments on mathoverflow.net/q/37679. Look up Hagedorn 2009 and papers referring to this. Recent work on long gaps between primes gives a lower bound much better than 2n. Also, it is enough consider the radical (largest square free factor) of n!. You might be more clear as to what you want a lower bound of. Gerhard "Does Know A Little Something" Paseman, 2019.01.14. $\endgroup$ Jan 15 '19 at 1:15
  • $\begingroup$ $n!-3\ $ and $\ n!-2\ $ are consecutive, less than $n!,\ $ and they are not coprime with $n!,\ $ for every $n\ge 3$. $\endgroup$
    – Wlod AA
    Jan 15 '19 at 2:19
  • 6
    $\begingroup$ The phrase you want to search for is the Jacobsthal function of $n!$. We know some things—for example, an upper bound is $O(n^2)$—but there's a lot of mystery still. $\endgroup$ Jan 15 '19 at 6:05
  • 1
    $\begingroup$ Is it essential that the consecutive numbers are less than $n!$? We always may reduce them modulo $n!$. $\endgroup$ Jan 15 '19 at 8:25
  • 1
    $\begingroup$ @WlodAA, I think you misunderstand the question. E.g., for $n=4$, the consecutive numbers $8,9,10$ are less than $n!$, and there are three of them, and that's more than the two consecutive numbers $21,22$ that you propose. $\endgroup$ Jan 15 '19 at 13:29
4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ To address the question directly, $L(89!)=233$, so no, the length can exceed 2n. Gerhard "Coming Back To The Point" Paseman, 2019.01.15. $\endgroup$ Jan 15 '19 at 17:13
  • $\begingroup$ Indeed, referring to the paper of Hagedorn, $L(43!)=89$. Gerhard "If We Only Knew Where..." Paseman, 2019.01.15. $\endgroup$ Jan 15 '19 at 17:39
  • $\begingroup$ thanks for the Answer, Gerhard. $\endgroup$
    – Ocean Yu
    Jan 16 '19 at 4:18
  • $\begingroup$ Gerhard, One more query, is it following paper you mentioned (by Hagedorn)? ams.org/journals/mcom/2009-78-266/S0025-5718-08-02166-2/… $\endgroup$
    – Ocean Yu
    Jan 17 '19 at 4:49
  • $\begingroup$ That looks like it. I am unaware of any other work of Hagedorn regarding Jacobsthal's function. Gerhard "Excepting Other Versions, Of Course" Paseman, 2019.01.16. $\endgroup$ Jan 17 '19 at 4:58
0
$\begingroup$

If I am not wrong, the question is totally trivial. I am finally writing "an answer" because I am finally tired of the comments which get ignored.

ANSWER: Let $\ n\ge 3.\ $ The largest two consecutive integers which are NOT relatively prime to $\ n!\ $ and which are $\ < n!\ $ are:

$$ n!-3\qquad\mbox{and}\qquad n!-2 $$

That's all.

$\endgroup$
2
  • 5
    $\begingroup$ I think they are looking for the maximal length of a set of consecutive integers such that all of them are not pairwise coprime to $n!$, not simply a maximal pair of integers such that neither is coprime to $n!$. $\endgroup$
    – user44191
    Jan 15 '19 at 9:49
  • $\begingroup$ @user44191, thank you, what a relief! $\endgroup$
    – Wlod AA
    Jan 15 '19 at 20:54

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.