Erik Westzynthius's cool upper bound argument: update? 
Version 2 of this writeup is
  available, and includes a newer and simple upper bound thanks to
  MathOverflow 88777 as
  well as indirect references to future writeups.  Details of further work
  will be found in these writeups.  GRP 2014.06.04.


In a paper of Erik Westzynthius,

Ueber die Verteilung der Zahlen, die zu den n ersten Primzahlen teilerfremd sind,
  Comm. Phys. Math. Soc. Sci. Fenn., Helsingfors (5) 25 (1931), 1-37

I saw the following upper bound argument.  Having never
studied sieve theory, I was quite impressed by it.  The goal is to bound from above
the quantity max $(q_{i+1} - q_i)$, where the $q_i$ are the positive integers in
increasing order which are relatively prime to $P_n$, the product of the first
n primes.  Here is a sketch of the argument.
Let $a$ and $x$ be real parameters, with $x > 0$ .  Consider the
integers in the open interval $(a, a+x)$, and call this set $H$.  Let us look
at the subsets of $H$ consisting of those integers which are a multiple of the
positive integer $t$; call the size of each such subset $I_t$.  Step 1 is to use
inclusion-exclusion to 
estimate $I_0$, the number of integers in the interval $(a, a+x)$ which are relatively 
prime to $P_n$. (I.e. count integers, throw out multiples of 2, throw out multiples
of 3, add in multiples of (2*3) to compensate, etc.)  We get
$I_0 = \sum_{t \in R} [I_t * (-1)^{\mu(t)}] $.
Here $R$ is the set of positive integers which are of the form 
(warning: sloppy notation) $\prod_{J \subset n} p_j$,
that is all integers whose prime factorizations have only primes less than
or equal to the nth prime, and those occuring only to at most the first power.
(More succinctly, $R$ is also the set of positive divisors of $P_n$.)  For
such a number $t \in R$, $\mu(t)$ is precisely the number of prime factors in $t$,
and $\mu$ is chosen to suggest the Moebius function whose value at such $t$ is 
$(-1)^{\mu(t)}$.  The equality is exact.
Step 2 is to replace $I_t$ with a linearized approximation plus an error term which
I will call $E(t)$.    This substitution gives:
$I_0 = \sum_{t \in R} [ (E(t) + x/t) * (-1)^{\mu(t)} ]$  .
Since the number of multiples of $t$ in the interval $(a, a + x)$ is roughly $x/t$,
the error term $E(t)$ is bounded in absolute value by $1$.  Step 3 will rewrite
the RHS and estimate it pessimistically: $E(t) * (-1)^{\mu(t)}$ will be replaced
by $-1$, and the alternating sum of $x/t$ terms can be rewritten as a product
involving terms of the form $(1 - 1/p_i)$, where $p_i$ is the $i$th prime. There are 
$2^n$ terms of the form $E(t)$, so one gets:
$I_0 \geq [x * \prod_{1 <= i <= n} (1 - 1/p_i) ] - 2^n  = x/Q - 2^n$ .
Here $Q$ is an abbreviation for $1$ divided by the product of the n terms $(1 - 1/p_i)$.
It is roughly log n  for large n.  Here comes the kicker.  Step 4
notes that steps 1 through 3 are essentially independent of $a$, and if $x$ can be
chosen so that $x/Q - 2^n > 0$, then $I_0 > 0$ which means at least one of the $q_i$
is in the interval $(a, a+x)$ when $a > 0$, and such $x$ would be an upper bound for 
$q_{i+1} - q_i$ which is independent of $i$. So choose $x = Q * 2^n$ plus epsilon.
I thought it a neat enough argument (especially the kicker)
that I am sharing it here with other non-students of sieve theory.  Now to the questions.
1) Is there any work done which improves the upper bound for $q_{i+1} - q_i$?
The answer to this is yes, since in a footnote Westzynthius shows how to
improve the bound to $Q * 2^{n-1}$ by counting odd multiples.  So I really want
to know if there are even better bounds out there, done by additional researchers.
I would expect a provable bound to be $Q * 2^g$,  where $g$ is something like a 
polynomial in log(n), but even having $g$ be n to a fractional power would be something.
2) Is there work done which uses something like the Bonferroni inequalities to
improve the above argument?
3) Did Westzynthius publish any other work (possibly nonmathematical) besides the
paper that includes the argument above?
Motivation: I am considering improvements to this argument which do establish
better upper bounds, and am wondering how to push the exponent from n - o(1) 
 down to poly(log(n)).  Especially, I want to know if I am rediscovering how
to replace n by cn for some $c < 1$, as opposed to discovering how to do it.
Gerhard "Ask Me About System Design" Paseman, 2010.09.03
 A: So it turns out that sieve theory already has some results that can give bounds for this problem. It took me a while to track down a paper that gives an explicit result, but I finally found this one.
Using the Bonferroni inequalities gives you what is called "Brun's pure sieve". According to Wikipedia, Brun's pure sieve gives a bound of the form $n^{b\log\log(n)}$ for some $b$.
According to the result in the paper, using the full power of Brun's sieve (which involves splitting up the primes we are sifting by into buckets of primes based on their sizes, throwing out terms of the inclusion-exclusion rule which have too many primes from the large buckets and then applying an inequality similar to the Bonferroni inequalities), we get that the number of numbers in an interval of length $x$ that are relatively prime to the first $n$ primes is at least
$x(\prod_{p\le p_n}(1-\frac{1}{p}))(1-2\frac{\lambda^{2b}e^{2\lambda}}{1-(\lambda e^{1+\lambda})^2}(1+o(1)))+O \left(p_n^{2b-1+\frac{2}{e^{2\lambda}-1}+\epsilon}\right)$,
where $b$ is an integer we get to choose, $\lambda$ is a positive real number we get to choose, and $\epsilon$ is greater than $0$.
If we plug in $b = 1$ and $\lambda = 0.2533$, we get that for sufficiently large $n$, any interval of size $O(n^{4.032})$ contains a number relatively prime to the first $n$ primes.
You can probably get better bounds with other sieves.
As far as what the best bound really is, I'm going to conjecture that the longest stretch of numbers that are not relatively prime to the first $n$ primes always has length less than $2p_n$. Computer search shows that this is true for $p_n \le 31$, and the worst case example for primes up to $31$ looks like this:
X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X
.X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X..X.
...X....X....X....X....X....X....X....X....X....X....X...
X......X......X......X......X......X......X......X......X
......X..........X..........X..........X..........X......
..X............X............X............X............X..
...........X................X................X...........
.........X..................X..................X.........
.....X......................X......................X.....
...........................X............................X
.............................X...........................

where the columns represent numbers, the rows represent primes, and an X means that the number corresponding to the column has been sieved out by the prime corresponding to the row.
A: I present the following as unverified information and would appreciate others who could confirm and supplement any of it.
Erik Westzynthius seems to have a middle name Johan.
I am hoping he is the only mathematically inclined Erik Westzynthius
in Finland, but there are several Erik Westzynthius' in Finnish
genealogy.  He was born in Helsinki on March 9, 1901, and had a sister
and later a wife, but I have not found any children of his, biologic or
academic.
There seem to be contributions by him to Scandinavian actuarial
publications as early as 1924, and his name appears (without Johan)
in a 1957 Scandinavian mathematical congress roster and also in the 
1978 ICM held in Helsinki.  He also seems to be acknowledged in a book on surgery
for his mathematical assistance; I am searching Google Books using the term "Erik Westzynthius" and am finding only snippets.  I have not found any other number theory
contributions from him.
The work referenced in the question was communicated to the journal
in September 1931 by R. Nevanlinna and E. Lindelof, but it is not clear 
that this work is what got Erik his fil. dr.; his result was a significant 
advance in the study of prime gaps however, so my money says it was the Finnish
equivalent of his doctoral dissertation.  Further, several reviews in
different languages of the result appear shortly thereafter, and it isn't 
long before Erdos and Rankin find improvements.
I am placing this entry as community wiki and invite the MathOverflow
community, especially the Scandinavian portion, to improve upon it.
Gerhard "Not Quite The Gentleman Scholar" Paseman, 2012.01.19
A: Here is a partial answer.  For those who want more information on this subject, 
Will Jagy has been kind enough to forward appropriate emails to me, to which I
respond.  I ask that you send requests about this to him to forward to me, until 
such time as I get a public email address set up.
For me, the key bit in the argument above is $E(t)$.  I put it in because I 
intended to follow up with a post that ran through the argument again, except
using only odd numbers (as per Westzynthius's footnote), and then certain thin sets
($S(k)$, the integers relatively prime to $P_k$:  I have not seen
this idea of applying thin sets to this sum elsewhere) . 
For example, using not the integers but instead the set $S(2)$
of numbers which are of the form $6m + 1$
or $6m - 1$, we can run through the argument again, except we replace $x/t$ by 
$\rho*x/t$
and $E(t)$ by $E_2(x/t)$.  $\rho$ is the density (= 1/3) of $S(2)$ in the integers,
 and
$E_2(x/t)$ is a more complicated error function which has a maximum value of 4/3. 
When the dust settles, we get for large $n$ a value for $x$ close to $Q * 2^{n-2}$.
Of course the idea of using even thinner sets now occurs.  To set that up, suppose
that $f(k)$ is an increasing function of $k$ to be constrained soon.  For notational
convenience, set $M(k)$ to be the maximum of the function $E_k(y)$ as $y$ ranges over
all real numbers.  Let us assume:
(subexponential growth in $k$ of $E_k(y)$ )  $M(k)*f(k) < 2^k$ .
Now with this assumption on $E_k$, the argument runs as follows: set up $I_0$
again with an inclusion exclusion argument, but count subsets $J_t$ of $S(k)$, the 
integers relatively prime to the $k$th primorial which are multiples of $t$.  $t$ now
ranges over the divisors of $P_n/P_k$.  We get a sum of $2^{n-k}$ terms card($J_t$),
each of which is replaced by a linear approximation as before, but now I change
notation slightly and use the error function $E_k(y)$, and replace $Q$ by $Q_n$. 
I collect terms as before to get 
$I_0 >= x/Q_n - \sum_{t \mid (P_n/P_k)} E_k(x/t)$ .
The smaller I can make this last sum, the better an upper bound I can get on $x$.
Using the growth assumption, I can bound the sum by $2^{n-k}*M(k)$, which is 
$2^n/f(k)$.
I can then get an upper bound of $2^n/f(n-1) * Q_n$ on $x$ just by assuming the worst
case values as well as the rather mild growth assumption.
However, it gets better than that.  One thing I do know is that $E_k(y)$ is bounded
by 1 when $y$ is less than 2.  So for many $k$ and many large $t$, I can safely choose
$x$ so that $E_k(x/t)$ is bounded by 1 for many $t$, so the sum looks like 
$2^{n-k} + D*(M(k) - 1)$, where $D$ can be much smaller than $2^{n-k}$.
The problem is that I do not know $M(k)$ or $E_k(y)$ that well.  It is likely that
$E_k(y)$ not only satisfies the subexponential growth assumption but also 
that $M(k)$ is
bounded by a low degree polynomial in $k$.  If this stronger assumption is true,
then $x$ will also be bounded by a low degree polynomial in $n$.  However, I want
something like the growth assumption to hold so that I can comfortably choose $x$.
Now that I have committed myself, I will grind through the calculations to come
up with an explicit bound.  I predict that $x <= n^2$, that is,
that the maximum gap in the sequence $S(n)$ is no bigger than $n^2$.
Now to try proving it.
Gerhard "Ask Me About System Design" Paseman, 2010.12.14
A: Since the question has acquired over 1000 views (of which I am sure less than half were done by me), I thought I would celebrate by giving an improvement that I promised half a year ago.  This is a refinement of a version I sent to several people; I invite the reader to submit corrections and/or criticism.
$\newcommand{piim}{\pi^{-1}(m)} \newcommand{sigim}{\sigma^{-1}(m)}$
The goal is to use Stevens's argument with improved estimates so as to reduce the exponent given by his method, which gives an upper bound on Jacobsthal's function.  The preliminaries have been covered in the question and another answer, so I start with the following: for $m$ a squarefree positive integer, $7 \lt n =\nu(m) =$ the number of distinct prime factors of $m$, $j(m)$ the value of Jacobsthal's function, one has after the use of inclusion-exclusion and the Bonferroni inequalties that there is an odd positive integer $s$ such that $SB/(P-T) \gt 0$, which would imply that $j(m) \leq SB/(P-T)$, where
$$SB= \sum_{1 \leq i \leq s} {{n} \choose {i}}\text{ , } 
P=\piim=\prod_{p \text{ prime, }p \mid m}(1 - 1/p) \text{, and } 
T = \sum_{s \lt k \leq n} (-1)^k \sum_{d \mid m, \nu(d)=k} 1/d . $$  The smaller a value of $s$ we can find, the better an upper bound we can form.
I will find $T'$ big enough that $T' > T$, yet small enough to get a nice value for $s$ and show that $P - T' > 0$.  Then I will massage 
$P - T'$ and $SB$ to give a slightly weaker upper bound that is
easier to write down.  
Let's write $\sigim = \sum_{1<=i<=n} 1/m_i$ with $m_i$ being the distinct prime divisors of $m$.  (I use $-1$ as a superscript, NOT as an exponent, in both $\piim$ and $\sigim$.)
Now $T$ is an alternating series, and for $k \gt 0$,
$$\sigim\sum_{d \mid m, \nu(d)=k} 1/d \gt 
(k+1)\sum_{d \mid m, \nu(d)=(k+1)} 1/d,$$ 
so if $s$ is odd and larger than $\sigim$, then it would suffice to replace $T$ by $D=\sum_{d \mid m, \nu(d)=s+1} 1/d$, provided we can show $D < P$.  Instead, we use an upper bound for $D$, namely $T' = \sigim^{s+1}/(s+1)!$, which follows by using the inequality above $s$-many times.
Let us find a value for $s$ such that $P(s+1)! > \sigim^{s+1} = (s+1)!T'$.  An earlier version of this result did some work to show that 
one could pick $s+1 >= 4\sigim > 0$, and in fact $4$ can sometimes be replaced by a smaller
constant.  The choice of $T'$ saves some work, and using $4$ will also
make things easier.
The following steps require $m \gt 1$, $s+1 \gt 1$, $s+1 \geq 4\sigim$, $0\lt P \lt 1$, and finally 
$e \lt P^{-1/\sigim} \leq 4 \in (e,4]$ (which is proved in [1]).
\begin{eqnarray*}
 & e \lt 4^{3/4} \text{, so } e* P^{-1/4\sigim}\lt e*4^{1/4} \lt 4, \\\\
\text{so} & \sigim \lt P^{1/4\sigim} 4\sigim/e \leq P^{1/s+1}((s+1)/e), \\\\
\text{so} & \sigim^{s+1} \lt P((s+1)/e)^{s+1} \lt P(s+1)! .
\end{eqnarray*}
Now that we have a candidate for $s$, let us choose the smallest
odd $s$ such that $s+1 \geq 4\sigim$.  Then
$$\frac{\sum_{1 \leq i \leq s} {{n}\choose{i}}}{P - \sigim^{s+1}/(s+1)!} \gt 0,$$
so this is an upper bound on $j(m)$.  Our choice of $s$ gives that
the denominator $P - T$ is actually larger than 
$(\sqrt{2\pi(s+1)} - 1)\sigim^{s+1}/(s+1)!$, and we can collapse the
summands in the binomial sum to get
$$j(m) \lt \frac{(s+1)![\sum_{0 \leq 2j \lt s} {{n+1} \choose {s-2j}}]}
   {(\sqrt{2\pi(s+1)} - 1)\sigim^{s+1}} .$$
Now for $\sigim \leq 1$ there are better bounds. In particular, given
$m_1$ is the smallest prime factor of $m$, one has a bound when
$\sigim \leq 1 + 1/m_1$ as
$j(m)< (2n - 1 - \sigim + 1/m_1)/(1 - \sigim + 1/m_1)$.  So the
estimate above is interesting primarily for $n > 7$.
If we compare this to Kanold's simpler bound ($2^n$ for all $m \gt 1$,
$2^\sqrt{n}$ for $n> e^{50}$), we find that this improves upon the $2^n$ bound for 
$n \gt 30$, and even improves upon the $2^\sqrt{n}$ bound for $n$ as small as
$22500$.  There are other bounds out there which improve upon this,
but do not make the constants explicit.
For $n>7$, we can upper bound the sum by a geometric series, and
replace it by a single binomial times a fudge factor which gets close
to 1 as n grows. Writing $K= 1 + s(s-1)/(n+2)(n + 3 - 2s)$,and rewriting the term $(s+1)! {{n+1}\choose{s}}$, one gets
$$\text{for } n \gt 7, j(m) \lt 
\frac{K (s+1)[(n-(s-3)/2)/\sigim]^s}{(\sqrt{2\pi(s+1)} - 1)\sigim}$$
where this is most useful for $ 1 \le \sigim $ and $s$ the smallest
odd integer greater tham $4\sigim$.
I may show some later refinements of this.  However,
$\sigim < 1 + \log\log n $ for $n > 7$ so the exponent $s$ grows very
slowly.  This will do for now.
[1] G. Paseman, "The Waltraud and Richard R. Paseman Theorem", private manuscript, March 2011.
Gerhard "Ask Me About System Design" Paseman, 2011.09.08
A: After studying Kanold's 1967 paper on Jacobsthal's function, (and being inspired by a preprint http://arxiv.org/abs/1208.5342 that I discuss below,) I found an argument, mostly very simple, which gives some nice results for the effort given.  While Kanold deserves some of the credit for the argument, I have yet to see a statement by him or by anyone else that gives these results, so I present them here.  (Kanold wrote several articles on Jacobsthal's function, many of which I am tracking down, which might have this argument.  I am happy to accept help in obtaining electronic copies of them.)  This is the post I promised over a few months ago in a supplement to a question of Timothy Foo, 
Analogues of Jacobsthal's function  .
For maximum ooh-aah effect, I assume $n$ is squarefree and has $k \gt 2$ prime factors, one of which I call Peter, or $p$ for short.Now $1+tn$ is coprime to $n$ for any integer $t$.  So are most integers of the form $1 + tn/p$, the exceptions being those that are multiples of $p$, and those multiples do not occur as consecutive terms.  Thus, every interval of length $2n/p (=g(p)n/p)$ has at least one integer coprime to $n$ of the form $1+tn/p$.
Let's go further with this.  Let $d \gt 1$ and divide $n$, and let $f=n/d$.  (Here I use $n$ squarefree to get $f$ coprime to $d$.)  Then numbers of the shape $1+tf$ form an arithmetic progression, are coprime to $f$, and (as can be seen by multiplying by $f$'s inverse in the ring of integers mod $d$) you can't pick $g(d)$ consecutive members of this progression without hitting something coprime to $d$ also.  So $g(n) \leq g(d)f = g(d)n/d$ .
While I'm here, let me sharpen the inequality, assuming $f \gt 1$ and $d \gt 1$ are coprime:
there are $\phi(f)$ totients $c$ of $f$ in the interval $[0,f]$, so I can repeat the argument with $c+tf$ instead of $1+tf$.  In the worst case, using all $\phi(f)$ progressions, I get $g(fd) \leq g(d)f - f + g(f)$, which mildly improves upon Kanold's bound $g(d)f -\phi(f)+1$, and matches it when $f$ is prime.  (Of course, for $n=fd$ I really want $g(n)$ to be near $O(g(d)+g(f))$, but I don't yet know how to show that with grade school arithmetic.)
How to use this inequality? Pick the largest divisor $d$ for which one can comfortably compute (a subquadratic in $k$ upper bound for) $g(d)$; I pick $d$ to contain most of the large prime factors of $n$: find prime $q$ dividing $n$ so that $\sigma^{-1}(d)=\sum_{p \text{ prime,} p|n, p \geq q} 1/p$ is less than $1 + 1/2q$; a routine argument yields $g(d)$ is $O(qk)$.  The ugly part is to show that $q \lt k^{0.5}$ (or else $d=n$), that $n/d \lt 2^{3q/2}$ which for large $k$ approaches $2^{3(k^{\epsilon + 1/e})/2}$, and that asymptotically $g(n)$ is $O(e^{k^{1/e}+D\log(k)})$.  This isn't hard after using one of Mertens's theorems and a Chebyshev function; it just isn't pretty.  (Also for smaller $n$, $\epsilon + 1/e$ can be close to $1/2$, but with patience $\epsilon$ will tend to zero.)
This gives a bound that is asymptotically better than my first efforts at this, improves slightly ($k^{0.5}$ replaced by $Ck^{0.37}+ D\log(k)$ on Kanold's bound of $2^\sqrt{k}$ for $k$ not too large, and does not need Kanold's requirement that $k > e^{50}$.  Up until one chooses $d$ and crunches the formulae, it is also a very elementary argument; I suspect even Legendre knew about using the multiplicative inverse to transform a general arithmetic progression to a (effectively) consecutive sequence of integers and still preserve the property of interest here, being a unit in a certain ring (or missing it by that much).  
(One of the benefits of letting this sit for a few months before posting is that I can add cool observations like: If I could get the inequality down to $g(n) \leq g(d)g(n/d)$, I could iterate the
above simple estimate to get an explicit bound of $O(k^c)$, where $c$ is a positive number less than 3.  Or like: using more advanced work combined with the above, I can get $g(n) 
\leq e^{k^{e^{-a}}}Ck^{a}$ for some integers $a$, which seems better than $Ck^{4\log\log{k}}$ if you don't look too closely.)
Further, one can use a computer to refine the method slightly and get estimates which do quite well for small values of $n$, where small here means $k<100$.  Asymptotically though, Stevens's and my upper bounds eventually outperform this bound.
Also, there has been a nice result out of University College Dublin that I will briefly interpret.  Fintan Costello and Paul Watts find a way of presenting a related function recursively, then numerically compute a lower bound on this function which implies an upper bound on Jacobsthal's function computed on some particular values.  I thank them for reminding me about using a multiplicative inverse mod $d$ for $f$, so they deserve a "piece of the action".
These authors work in (and sometimes away from) the integer interval $BM = [b+1,b+2,\ldots,b+m]$.  Given squarefree $n$ and its distinct prime factors, listed in some order as $q_1$ to $q_k$, define $Q_i$ as  $\prod_{0 \lt j \leq i} q_j$. One approach to computing the size $\pi(b,m,n)$ of the set $CP(b,m,n)$ which has those integers in $BM$ coprime to $n$ is to do the standard inclusion-exclusion argument: if we represent by $F(b,m,d)$ the multiples of $d$ in $BM$, and say there are $f(b,m,d)$ many such multiples, and abuse some notation, I then write
$CP(b,m,n) = \sum_{d | n} sgn(d,F(b,m,d))$ .  Here $sgn$ is to suggest adding elements of the set $F(b,m,d)$ if $d$ has an even number of prime factors, and subtracting them instead when $d$ has an odd number of prime factors.
To set up for the recurrent expression, Costello and Watts use just some of the terms on the right hand side of the abused equation, and reorganize the rest of the terms.  In my interpretation of their work, they start with the multiset identity
$$CP(b,m,n) \cup \biguplus_{0 \lt i \leq k} F(b,m,q_i) =
BM \uplus  \biguplus_{0 \lt i \lt j \leq k} RCP(i,j)$$
where $RCP(i,j)$ is $F(b,m,q_iq_j) \cap CP(b,m,Q_{i-1})$, or the subset of $BM$ which has those multiples of $q_iq_j$ whose soonest prime factor in common with $n$ is $q_i$.  
One sees this identity holds by considering a member of $BM$ which has exactly $t$ distinct prime factors in common with $n$.
If $t$ is $0$, then the member occurs only once in $CP(b,m,n)$ and similarly only once in $BM$.  Otherwise, it occurs exactly $t$ times in the left hand side in $t$ distinct terms $F(b,m,q_i)$, and if $l$ is soonest such that $q_l$ is a prime factor of the member, the member occurs only once in each of $t-1$ sets
$RCP(l,j)$ (remember $l$ comes sooner than $j$) and only once in $BM$.
Now the term $RCP(i,j)$ is a subset of an arithmetic progression $A$ with common difference $q_iq_j$. By using the technique above of multiplying by a suitable inverse of $q_iq_j$ in the ring of integers mod $Q_{i-1}$, $A$ corresponds with an integer interval starting near some integer $c_{ijbm}$ of length $f(b,m,q_iq_j)$ which preserves the coprimality status with respect to $Q_{i-1}$: to wit, the size of $RCP(i,j)$ is $\pi(c_{ijbm},f(b,m,q_iq_j),Q_{i-1})$.  Using the $\pi$ term for the size of $CP$ and translating the other sets to numbers gives the numerical recurrent formula of Costello and Watts:
$$\pi(b,m,n) = m - \sum_{0 \lt i \leq k} f(b,m,q_i) 
+ \sum_{0 \lt i \lt j \leq k} \pi(c_{ijbm},f(b,m,q_iq_j),Q_{i-1})$$.
Following work of Hagedorn who computed $h(k)=g(P_k)$ for $k$ less than 50, where $P_k$ is the $k$th primorial, Costello and Watts use their formula and some analysis of coincidence of prime residues to compute an inequality for $\pi_{min}(m,n)$ which is the minimum over all integers $b$ of $\pi(b,m,n)$.  They underestimate $f(b,m,q_iq_j)$ by $\lfloor m/q_iq_j \rfloor$, ignore the $c$'s by using $\pi_min$, pull out the $i=1$ terms from the double sum and rewrite that portion to include a term $E$, depending only on $m$ and the $p_i$, which arises from looking at when estimates for the sizes of the $F(b,m,p_i)$  and $F(b,m,2p_i)$ sets can be improved, and come up with (a refined version, using $p$'s for $q$'s, of) the inequality 
$$m - \sum_{0 \lt i \leq k}  \lceil \frac{m}{p_i} \rceil + \sum_{1 \lt i \leq k} \lfloor \frac{m}{2p_i} \rfloor + E + \sum_{1 \lt i \lt j \leq k} \pi_{min}(\lfloor \frac{m}{p_ip_j} \rfloor,P_{i-1}) \leq \pi_{min}(m,P_k)$$.
With this inequality, Costello and Watts compute $\pi_{low}$, a lower bound approximation to $\pi_{min}$.  Since $h(k) \leq m$ iff $\pi_{min}(m,P_k) \gt 0$, computing $\pi_{low}(m,P_k)$ for various $m$ will give an upper bound on $h(k)$.  They say their computations for $k \leq 10000$ suggest $h(k) \leq Ck^2 \log k$, where $C$ is a constant less than $0.3$ .  Although this data is achieved using data from Hagedorn's work, even without that their algorithm yields values which are a vast improvement on known and easily computable bounds, even the ones listed above.
One item to explore is how an algorithm based on this approximation will perform given different orderings of the prime factors.  I suspect that letting the larger primes come first will give tighter results.  Another item to explore is to see if there is a better term $F$ that will supplant $E$ and some of the recurrent terms in the double sum.  The idea of rewriting the $\pi$ function recursively, while not new, is given new life in this double sum form, and suggests revisiting some old approaches with an eye toward computability.
Gerhard "Ask Me About Coprime Integers" Paseman, 2013.02.05
