# Maximum length of sequence of non-coprimes of $N$ - least upper bound for Jacobsthal's function

I am looking at the length of the longest sequences of adjacent integers that are not coprime to $N$ for very large $N$.

Let $F_N$ be the set of integers less than $N$ which are not coprime with $N$: $$F_N = \{x : x \in \mathbb{N}, x \lt N , \gcd(x,N)=1\}$$ Let $g(N)$ be the length of the longest sequence of adjacent integers in $F_N$.

IE something like: $$g(N) = \max (i\in \mathbb{N}) : \exists a\in F_n : \forall b : a \le b \lt a+i, b\in F_N$$ What is the least upper bound on $g(N)$, i.e. the maximum length of a sequence of adjacent numbers in $F_N$?

Some direct calculation suggests that $g(N)$ steps up when $N$ is primorial, so if $P_i$ is the primorial sequence, then: $$\forall N \lt P_i, g(N) \lt g(P_i)$$ I have no proof of this, but it suggests $g(P_i)$ may be useful in finding a least upper bound.

There are $N - \phi (N)$ non-coprimes of $N$ less than $N$ (where $\phi$ represents Euler's totient function, labelled 'phi' in the table below). The assumption that these are evenly spread giving $$g(N) \approx \frac N {\phi (N)}$$ is clearly wrong.

Better estimates (for the primorial values of $N$ only) seem to be: $$g(N) \approx 2 \log(N)$$ and $g(N) \approx$ twice the highest prime factor of $N$. However, these are untested outside the data below, and again I have no proof.

Below is a table of $g(N)$ and $\phi(N)$ of the primorials:

 N (Primorial)   Highest prime   phi (N)    g(N)
2               2               0          1
6               3               1          3
30              5               7          5
210             7               47         9
2310            11              479        13
30030           13              5759       21
510510          17              92159      25
9699690         19              1658879    33
300690390       21              49766399   39


Edit:

As Gerry Myerson kindly points out in the comments, $g(N)$ is similar to Jacobsthal's function, $j(N)$ series here where $j(N) = g(N)+1$.

Several online sources point to a proof by H. Iwaniec in 'On the problem of Jacobsthal, Demonstratio Math. 11, 225–231, (1978)' (original not available online) that: $$j(N) \ll \log \log (N)$$ Whilst this might be true in asymptotic terms, it's trivially not true for the primorials above, and the sequence appears closer to $\log (N)$ than $\log \log(N)$. So the question remains open.

• The smallest factor of $N$ is not an upper bound: for $N = 6$, the smallest factor is $2$, but $g(6) = 3$ as there are three consecutive numbers in $F_6$, namely $2, 3, 4$. – ShreevatsaR Jun 15 '13 at 18:25
• Thanks - thus proving every sentence starting with the words 'clearly' is wrong. I've removed that bit. – David Verren Jun 15 '13 at 18:31
• Your statement should clearly read "Clearly, every sentence starting with the words 'clearly' is wrong." – marty cohen Jun 15 '13 at 18:35
• $g(N)$ is tabulated at oeis.org/A058989 and some references are given. – Gerry Myerson Jun 16 '13 at 11:31
• I don't think that's $g(N)$ as the input to that sequence is the $N$'th prime. However, that does provide a link to the Jacobsthal function $j(N)$, and it seems $$j(N)=g(N)+1$$ This gives $$j(n) = O(log^2(N))$$but I'm not sure that's an upper bound let alone a least upper bound. – David Verren Jun 16 '13 at 12:20