For $n \geq 3$ let $r(n)$ be the previous prime to $n$; i.e., the largest prime strictly less than $n$. For example, $r(3) = 2$, $r(10) = 7$, and so on.

I have noticed that $r(n^p)$ is very close to $n^p$. In fact, I suspect that $$\lim_{n\to\infty}\frac{r(n^p)}{n^p} = 1$$ for any positive integer power $p$, where the convergence is faster if $p$ is big. Is this true? Are there effective bounds on the rate of convergence? Is there a simple proof of this fact?

Here's an argument that doesn't work: By Bertrand's postulate, there exists a prime between $n^p / 2$ and $n^p$ (roughly). Therefore $$\frac{r(n^p)}{n^p} \geq \frac{1}{2}.$$ But this is pretty far from $1$.

I think that I can prove this using some fancy number theory results, but they seem like sledgehammers. I'd like something simpler.

  • $\begingroup$ so mersenne numbers and fermat numbers aren't in the picture. $\endgroup$
    – user645636
    Nov 23, 2019 at 2:07
  • 3
    $\begingroup$ The fact that the limit approaches $1$ implies that the difference between a large prime and a large power can be a negligibly small fraction of that large power, but NOT that the difference can be made arbitrarily small, such as $<50$. Also, I don't see what is specially interesting about powers. Refinements to Bertrand's postulate suggest that $\lim_{n\to\infty}\frac{r(n)}{n} = 1$ $\endgroup$ Nov 23, 2019 at 3:08
  • $\begingroup$ @RoddyMacPhee - why are Mersenne-numbers/-primes out of the picture? $\endgroup$ Nov 23, 2019 at 22:17
  • $\begingroup$ @Gottfried , because them being infinite in the primes, would show there are infinitely many 1 away. $\endgroup$
    – user645636
    Nov 24, 2019 at 0:19
  • $\begingroup$ @RoddyMacPhee - yes, but why then out of the picture instead of in the picture. Mersenne-primes are perfect exemplars for what the OP is asking for, or not? $\endgroup$ Nov 24, 2019 at 0:26

3 Answers 3


Notice that $r(m)=p_{\pi(m-1)}$ where $p_m$ is the $m$th prime number. (Since $m=n^p$ won’t be prime in our case we will always have: $\pi(m)=\pi(m-1)$ and we can write everything more conveniently as $r(m)=p_{\pi(m)}$.)

Look at the number of primes less than $n^p$: that would be $\pi(n^p)\approx\frac{n^p}{\log(n^p)}$. Now you are looking for approximately the $\pi(n^p)$th prime number and $p_m\approx\,m\log(m)$, thus $p_{\pi(n^p)}\approx\,n^p-n^p\frac{\log(\log(n^p))}{\log(n^p)}$. Now your function is essentially $p_{\pi(n^p)}/n^p\approx{}1-\frac{\log(\log(n^p))}{\log(n^p)}$ which converges to $1$.

  • 1
    $\begingroup$ Why isn't this a rigorous argument already? It seems pretty plausible to me! (I'm not immediately sure how to make the convergence effective from this, though.) $\endgroup$
    – Robert D-B
    Nov 22, 2019 at 22:36
  • 1
    $\begingroup$ The limit being equal to 1 is immediate from the $\approx$ notation which implies that the two sides belong in the same asymptotic class as $n\to\infty$. The only issue with the proof is that it doesn’t use the form $n^p$ at all! It simply holds for $n$ and $r(n^p)/n^p$ obviously converges too as a subsequence. $\endgroup$ Nov 22, 2019 at 22:43
  • 3
    $\begingroup$ Technically, $r(m)=p_{\pi(m-1)}$. $\endgroup$
    – J.G.
    Nov 22, 2019 at 22:46
  • $\begingroup$ @J.G. Indeed, hopefully the asymptotic notation and the limits at the end save the day... $\endgroup$ Nov 22, 2019 at 22:49

Though Μάρκος posted a great answer, for completeness I'll post the complicated proof that I know.

It suffices to show that there exists a prime between $x$ and $(1 + b(x))x$ for sufficiently large $x$, where $b(x) \to 0$ as $x \to \infty$. (Then $r(n^p) / n^p \geq \frac{1}{1 + b(n^p)}$, and letting $n \to \infty$ yields the result.) By some complicated number theory, we can take $b(x) = 1 + 1 / (2 \log^2 x)$ for $x \geq 3275$. This gives $$\frac{r(n^p)}{n^p} \geq \frac{1}{1 + \frac{1}{2 \log^2 n^p}}$$ for $n$ sufficiently large. This says that the limit is $1$, and that it approaches $1$ quicker if $p$ is large.

  • $\begingroup$ Brutal. Correct, but brutal. $\endgroup$
    – ViHdzP
    Nov 23, 2019 at 2:56
  • 1
    $\begingroup$ It's worth noting that your sufficient condition can be proved from the prime number theorem rather than Pierre Dusart's result - I added an update to my answer to cover this. $\endgroup$
    – Ivan
    Nov 23, 2019 at 16:30

To get the limit you only need the prime number theorem

$$\lim_{n\rightarrow \infty}\pi(n)/(n/\ln n)=1 \tag 1$$

but the deduction is a bit messy.

From (1) you can deduce that for any $\epsilon^{'}>0$ $$\lim_{n\rightarrow \infty}\pi(n(1+\epsilon^{'}))/(n(1+\epsilon^{'})/\ln n(1+\epsilon^{'}))=1$$ Now $\lim_{n\rightarrow \infty}\ln n(1+\epsilon^{'})/\ln n=1$ so $$\lim_{n\rightarrow \infty}\pi(n(1+\epsilon^{'}))/(n(1+\epsilon^{'})/\ln n)=1$$

This means that for any $\epsilon>0$ $\exists N \in \mathbb{N}$ s.t. $\forall n>N$ the following two inequalities hold:

\begin{align} (1-\epsilon)(n/\ln(n))&<\pi(n)& &<(1+\epsilon)(n/\ln(n)) \\ (1-\epsilon)(1+\epsilon^{'})(n/\ln(n))&<\pi(n(1+\epsilon^{'}))& &<(1+\epsilon)(1+\epsilon^{'})(n/\ln(n)) \end{align}

Subtracting the two inequalities we obtain after some simplification:


This clearly implies that $$\lim_{n\rightarrow \infty}\frac{\pi(n(1+\epsilon^{'}))-\pi(n)}{(n/\ln(n))}=\epsilon^{'}$$ and in particular that $$\lim_{n\rightarrow \infty}\pi(n(1+\epsilon^{'}))-\pi(n)=\infty$$

This implies that for any $\epsilon^{'}>0$ $\pi(n(1+\epsilon^{'}))-\pi(n)>1$ for large enough $n$ and hence that there exists a prime $p$ with $n<p<n(1+\epsilon^{'}).$

Clearly then we have for $\epsilon^{'}>0$ and all large enough n $$n<r(n)<n(1+\epsilon^{'})$$ and thus also for any fixed $p\in \mathbb{N}$ $$1-\epsilon^{'}<\frac{1}{1+\epsilon^{'}}<n^p/r(n^p)<1$$.

which implies that $$\lim_{n\rightarrow \infty}n^p/r(n^p)=1$$

Update to show that the rwbogl's sufficient condition can be proved from the prime number theorem rather than Pierre Dusart's result.

From the PNT I showed that for any $\epsilon>0$ there exists a prime $p$ with $n<p<n(1+\epsilon)$ for some $n=N(\epsilon)$ where $N$ is strictly increasing as $\epsilon$ decreases to $0$. If we set $g(n)=N(1/n)$ where $n\in\mathbb{N}$ then $g\in\mathbb{N}$ increases monotonically and hence possesses a monotonically increasing pseudo-inverse $g^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ s.t. $g(g^{-1}(x))=x$ for all $x\in\mathbb{N}.$

Substituting we have for any $n\in\mathbb{N}$ there exists a prime $p$ with $g(n)<p<g(n)(1+1/n)$. Setting $n=g^{-1}(x)$, $x\in\mathbb{Z}$ we have for any $x\in\mathbb{N}$ there exists a prime $p$ with $$x<p<x(1+1/g^{-1}(x))=x(1+f(x))$$ where $f(x)=1/g^{-1}(x)$ which decreases monotonically to 0 as $x\rightarrow \infty$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .