# Smallest integer not divisible by integers in a finite set

Hello all, if $a_1,a_2, \ldots a_t$ are $t$ integers $\geq 2$, the set $G(a_1,a_2, \ldots a_t)=\lbrace N \geq 1 |$ In any sequence of $N$ consecutive integers there is at least one not divisible by any of $a_1,a_2, \ldots a_t\rbrace$ is nonempty (it contains $a_1a_2 \ldots a_t$) so it has a minimal element which we denote by $g(a_1,a_2, \ldots a_t)$.

Question 1 : Is there a uniform bound $\gamma (t)$, depending only on $t$, such that $\gamma (t) \geq g(a_1,a_2, \ldots a_t)$ for any $a_1,a_2, \ldots a_t$ ? For example, we may take $\gamma(2)=4$.

Question 2 : If $\gamma$ is well-defined, are any asymptotics known about $\gamma(t)$ ?

-
It seems sieve techniques could give you a quick rough bound $\gamma(t)$, but I don't know a good way to make this precise off hand and someone else will probably answer before I return. – Jonas Meyer Mar 8 '10 at 21:41
It might be worthwhile to start with the special cases where $a_k = k$ or where $a_k$ is the $k$th prime. I don't know the answer, though. – Michael Lugo Mar 8 '10 at 22:48
If $p_1,p_2,\dots,p_t$ are the first $t$ primes, then $g(p_1,p_2,\dots,p_t)-1$ is sequence A058989 at the Online Encyclopedia of Integer Sequences, oeis.org/A058989 – Gerry Myerson Mar 8 '10 at 22:50
@ Michael : also, if we take the best possible $\gamma(t)$ (so that it is a maximum) one may wonder where this maximum is attained ; is it when $a_k$ is the $k$-th prime ? – Ewan Delanoy Mar 9 '10 at 4:00
Ewan, it seems that way to me, but I am not basing that on deep insight. It is immediate that we can assume the $a_k$'s are prime, because if $p_k$ is a prime factor of $a_k$, then $G(p_1,\ldots,p_t)\subseteq G(a_1,\ldots,a_t)$ and thus $g(p_1,\ldots,p_t)\geq g(a_1,\ldots,a_t)$. Then it seems you can count how many numbers would be lost from a string of $M$ consecutive integers by first removing factors of $p_1$, then $p_2$, and so on, and it seems you can't do worse than the case when $p_k$= the $k$-th prime. – Jonas Meyer Mar 9 '10 at 4:15

Given an integer $n$, the Jacobsthal function $g(n)$ is the least integer, so that among any $g(n)$ consecutive integers $a,a+1,\dots,a+g(n)-1$ there is at least one that is coprime to $n$. Let $\nu(n)$ count the distinct prime factors of $n$. You can define $$C(r)=\max_{\nu(n)=r} g(n)$$ and as Jonas Meyer points out in the comments this is precisely $C(t)=\gamma (t)$ (i.e. it is enough to consider when all $a_i$ are prime).

For the bounds $$\frac{c_1t (\log t)^2 \log \log \log t}{(\log\log t)^2}\le C(t)\le c_2 t^{c_3}$$ see the paper "On the integers relatively prime to n and on a number-theoretic function considered by Jacobsthal"" by Erdos. I don't know if there are better bounds.

-
Of course $r$ should be $t$ (or $t$ should be $r$) in that 2nd display. The Erdos paper is available at renyi.hu/~p_erdos/1962-12.pdf Erdos attributes the 1st inequality to Rankin, The difference between consecutive prime numbers, J London Math Soc 13 (1938) 242-244. The 2nd inequality he says "follows easily from Brun's method." – Gerry Myerson Mar 10 '10 at 1:54

Thomas Hagedorn has a short survey on results related to the Jacobsthal function, as well as recent computations for a_i being the first t primes for t up to 50 . It is at http://www.tcnj.edu/~hagedorn/papers/JacobPaper.pdf . In his section 1, Hagedorn cites a result of Iwaniec which gives an asymptotic upper bound of order O(t log(t))^2, and he cites a more explicit upper bound that was given by Stevens as 2t^(2 + 2elog(t)). (He also cites a lower bound by Pintz which is a mild improvement on the Erdos lower bound.) I am working on replacing the bound in Stevens' result by something asymptotically smaller (involving log(log(tlog(t))). I will post it as an answer to Erik Westzynthius's cool upper bound argument: update? when I am confident it is valid.

UPDATE 2011.02.25 I have posted an improvement of Stevens's result as an answer to the linked question above. I welcome a review of it.END UPDATE 2011.02.25