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   


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.

  • $\begingroup$ 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$. $\endgroup$ – ShreevatsaR Jun 15 '13 at 18:25
  • $\begingroup$ Thanks - thus proving every sentence starting with the words 'clearly' is wrong. I've removed that bit. $\endgroup$ – David Verren Jun 15 '13 at 18:31
  • 1
    $\begingroup$ Your statement should clearly read "Clearly, every sentence starting with the words 'clearly' is wrong." $\endgroup$ – marty cohen Jun 15 '13 at 18:35
  • 2
    $\begingroup$ $g(N)$ is tabulated at oeis.org/A058989 and some references are given. $\endgroup$ – Gerry Myerson Jun 16 '13 at 11:31
  • $\begingroup$ 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. $\endgroup$ – David Verren Jun 16 '13 at 12:20

Your Answer

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

Browse other questions tagged or ask your own question.