# 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

## 2 Answers

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

Gerhard "Ask Me About System Design" Paseman, 2011.02.13

• I'm having trouble seeing how these estimates relate to those in the Erdos paper cited by Gjergji Zaimi. – Gerry Myerson Feb 14 '11 at 11:33
• The Jacobsthal function j(n) has values which depend heavily on the number of distinct prime factors of n. I am using t for the number of distinct prime factors of n. Hagedorn is interested in j(P_t), which is evaluated at the (teeth?) primorial, but Stevens assumes only that t (actually Stevens uses k) is the number of distinct prime factors for his estimate. Stevens' estimate is worse asymptotically than Erdos', but is explicit. The same will be true for my replacement. Gerhard "Ask Me About System Design" Paseman, 2011.02.14 – Gerhard Paseman Feb 14 '11 at 16:59
• Maybe this is a good place to note a new paper, L. Hajdu and N. Saradha, Disproof of a conjecture of Jacobsthal, Math. Comp., posted at ams.org/journals/mcom/0000-000-00/S0025-5718-2012-02581-6/… – Gerry Myerson Apr 2 '12 at 7:23