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$ \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 1 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\$.