# Are there primes arbitrarily close to powers?

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.

• so mersenne numbers and fermat numbers aren't in the picture.
– user645636
Nov 23, 2019 at 2:07
• 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$ Nov 23, 2019 at 3:08
• @RoddyMacPhee - why are Mersenne-numbers/-primes out of the picture? Nov 23, 2019 at 22:17
• @Gottfried , because them being infinite in the primes, would show there are infinitely many 1 away.
– user645636
Nov 24, 2019 at 0:19
• @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? Nov 24, 2019 at 0:26

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

• 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.) Nov 22, 2019 at 22:36
• 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. Nov 22, 2019 at 22:43
• Technically, $r(m)=p_{\pi(m-1)}$.
– J.G.
Nov 22, 2019 at 22:46
• @J.G. Indeed, hopefully the asymptotic notation and the limits at the end save the day... 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.

• Brutal. Correct, but brutal. Nov 23, 2019 at 2:56
• 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.
– 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:

$$\{\epsilon^{'}-\epsilon(\epsilon^{'}+2)\}<\frac{\pi(n(1+\epsilon^{'}))-\pi(n)}{(n/\ln(n))}<\{\epsilon^{'}+\epsilon(\epsilon^{'}+2)\}$$

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

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

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