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

704 Views Asked by At

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.