# Finding 8 co-primes $\le 2^n$

We can find 8 co-prime integers $\le 2^n$ for sufficiently large $n$. I'm looking for asymptotic bounds for the minimum distance away from $2^n$ we have to go before finding 8 co-primes.

In other words, if we take $n=5$, we'd like to find a set of 8 co-prime naturals as close to $2^5=32$ as possible, but all less than or equal to 32. A potential set is $\{17,19,22,23,25,27,29,31\}$. I don't know if these are all as close to 32 as we can get, but they're close. They're within $14 \approx O(2^{(n-1)})$. I'd like to know how close we can get to $2^n$ for large $n$, in the worst case.

SOME BACKGROUND

According to Wikipedia, Ingham showed that there is a prime between $n^3$ and $(n+1)^3$ for sufficiently large $n$, if his conjecture holds.

This would mean that there are 8 primes between $(2^n-8)^3$ and $(2^n)^3$. Obviously we should be able to find 8 co-primes that are even closer to $(2^n)^3 = 2^{3n}$. I'm looking for an asymptotic bounds for these 8 primes.

Additionally, Wikipedia gives the probability that any two naturals are co-prime as $\frac{6}{\pi^2} \approx 61 \%$. This could get us some sort of probabilistic bounds.

• I note that $(2^n-8)^3 \approx 2^{3n} - (3)8(2^n)^2$, and $(3)8(2^n)^2 = O((2^{3n})^{2/3})$ – Matt Groff Jun 7 '16 at 1:33

For a general integer $x$, consider the following eight quantities: $$20!x + 2, 20!x + 3, 20!x + 5, 20!x + 7, 20!x + 11, 20!x + 13, 20!x + 17, 20!x + 19.$$ I claim that these are all pairwise relatively prime. Consider $20!x + p$ and $20!x + q$, for $p < q$: \begin{align*} (20!x + p, 20!x + q) &= (20!x + p, q-p) \\ &= (p,q-p) \text{ since } q-p \le 20 \\ &= (p,q) \\ &= 1 \text{ since } p, q \text{ are distinct primes}. \end{align*}
It follows that there exist eight pairwise relatively prime quantities between $2^n - 20! - 20$ and $2^n$, for any $n$. In particular, to answer your question, there exist eight co-primes $\boldsymbol{O(1)}$ away from $2^n$.
• +1 The constant $20!$ can be improved. Since only the property that $20!$ is divisible by all differences between offsets $p-q$ is used, we can immediately replace it by the GCD of these same offset differences, which turns out to be $16\cdot 9\cdot 5\cdot 7\cdot 11\cdot 17 = 942480$. An even smaller GCD of offset differences is given by the choice of offsets in the Question, $17,19,\ldots,31$, namely $2520$. – hardmath Jun 7 '16 at 7:36
• No one can improve $O(1)$, however. Nicely done. – hardmath Jun 7 '16 at 8:03