7
$\begingroup$

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)$ ?

Improve this question
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Jonas Meyer
    Commented Mar 8, 2010 at 21:41
  • $\begingroup$ 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. $\endgroup$
    – Michael Lugo
    Commented Mar 8, 2010 at 22:48
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerry Myerson
    Commented Mar 8, 2010 at 22:50
  • $\begingroup$ @ 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 ? $\endgroup$
    – Ewan Delanoy
    Commented Mar 9, 2010 at 4:00
  • $\begingroup$ 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. $\endgroup$
    – Jonas Meyer
    Commented Mar 9, 2010 at 4:15

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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." $\endgroup$
    – Gerry Myerson
    Commented Mar 10, 2010 at 1:54
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ I'm having trouble seeing how these estimates relate to those in the Erdos paper cited by Gjergji Zaimi. $\endgroup$
    – Gerry Myerson
    Commented Feb 14, 2011 at 11:33
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Feb 14, 2011 at 16:59
  • $\begingroup$ 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/… $\endgroup$
    – Gerry Myerson
    Commented Apr 2, 2012 at 7:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .