Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
$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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.