3
$\begingroup$

Is there a result in the spirit of Bertrand-Chebyshev which talks about the existence of prime powers between n and 2n (or 3n or something like that) for n large?

$\endgroup$

3 Answers 3

7
$\begingroup$

It follows from the prime number theorem that for fixed $k$, provided $n$ is sufficiently large, there is a prime $p$ such that $p^k$ is between $n$ and $2n$. Does this answer your question?

$\endgroup$
2
  • $\begingroup$ Thank you very much for your quick answer. Yes, it answers the question, and it goes to show the power of the PNT. $\endgroup$
    – Chebolu
    Apr 27, 2011 at 16:01
  • 1
    $\begingroup$ I wonder if there is an elementary proof of this without using PNT, like Erdős' proof of Bertrand's Postulate? $\endgroup$
    – Tony Huynh
    Apr 27, 2011 at 17:24
17
$\begingroup$

Actually there is a power of 2. It goes to show the power of binary arithmetic ... : write 2n in binary and write zeroes after the initial one.

$\endgroup$
2
  • 2
    $\begingroup$ In other words, if $2^{k - 1}$ is the largest power of 2 less than n, then $n \leq 2^k < 2n$? $\endgroup$
    – Ryan Reich
    Apr 27, 2011 at 18:14
  • $\begingroup$ Yes, you said it. $\endgroup$ Apr 27, 2011 at 18:43
6
$\begingroup$

For fixed $k$, the existence of a prime power $p^k$ between $n$ and $2n$ is (asymptotically) equivalent to the existence of a prime $p$ between $m$ and $\sqrt[k]{2} m$ where $m = \sqrt[k]{n}$. Bachraoui gives an elementary proof here that there exists a prime between $m$ and $\frac{3}{2} m$ for sufficiently large $m$.

I remember reading on MO that it is known that similar elementary proofs exist for showing the existence of primes between $m$ and $(1 + \epsilon) m$ for any $\epsilon > 0$ and, furthermore, that the existence of these proofs itself depends on the PNT. However, I can't track down where I read this.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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