2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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})$ $\endgroup$ – Matt Groff Jun 7 '16 at 1:33
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ +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$. $\endgroup$ – hardmath Jun 7 '16 at 7:36
  • $\begingroup$ @hardmath Yes, I didn't try to optimize the constant. That's a good observation. $\endgroup$ – 6005 Jun 7 '16 at 7:58
  • $\begingroup$ No one can improve $O(1)$, however. Nicely done. $\endgroup$ – hardmath Jun 7 '16 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.