Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What would an asymptotic location of a first prime number bigger than $n^n$? where $n$ is some nonzero natural number?

Also, what would be some ways to find a such number?

share|cite|improve this question
You have exactly the same problem as in your previous question. There is no systematic practical way to do this. Michael Hardy and Gerry Myerson both pointed this out. The addition of the condition "minimal such that p > n^n" doesn't change anything! – daniel Nov 6 '12 at 22:15
up vote 2 down vote accepted

The Prime Number Theorem asserts that in the large we will have about $\frac{n^n}{\log n^n}$ primes less than $n^n,$ the largest being $p_1 =p(\pi(n^n)),$ and then another one after $n^n,~ p_2 = p(\pi(n^n)+1).$ There is in general no simple scheme to find either the last prime before $n^n$ or the next one, $p(\pi(n^n)+1).$ Discussion of how far away $p_2$ is from $p_1$ is generally found under "prime gap."

Erdos showed that the limit $\frac{p_n}{p_{n+1}}= 1$, discussed here.

The OP asks for asymptotics. I hope the information in the comments below gives an idea. There are several categories of asymptotic results. Two are mentioned. The most recent one I found in the spirit of Tchudakov was Baker (2001), and then there are results similar to Bertrand's postulate such as Schoenfeld's (1976).

The best result (I know of) not assuming the Riemann Hypothesis is Dusart (2010): for n > 396738 there is a prime on $(n, [1 + 1/(25\ln^2n)]n).$

share|cite|improve this answer
That's not true. Heuristically, an integer near $n^n$ should have probability $1/\log(n^n)$ of being prime, so $p(\pi(n^n)+1)$ should be approximately $n^n + \log(n^n)$. Certainly it is $\Theta(n^n)$. – Robert Israel Nov 6 '12 at 22:32
Yes, there is a limit to how far we should have to search. So if we have a prime in the vicinity of n^n, we expect another one in the neighborhood you mention--I think Erdos' relation highlights the difficulty. Also, my answer is in light of OP's earlier question in same vein. If you think there's a significant problem with the answer, let me know and I will ask OP to un-accept so I can either edit or delete. Thanks. – daniel Nov 6 '12 at 23:09
There is a constant $\theta < 1$ (which according to Chudakov can be taken to be $3/4+\epsilon$ for any $\epsilon>0$) such that for $k$ sufficiently large there is always a prime between $k$ and $k + k^\theta$, thus in this case $n^n$ and $n^n + n^{\theta n}$. – Robert Israel Nov 6 '12 at 23:28
We also have Schoenfeld: there is a prime on $(n, n(1+ 1/16597))$ for n > 2010760. But it's still no easy trick to find one. – daniel Nov 6 '12 at 23:39
Re $\theta:$ Baker, R. C.; Harman, G.; Pintz, G.; Pintz, J. "The difference Between Consecutive Primes, II". Proceedings of the London Mathematical Society (2001) 83 (3): 532–562. Constant improved to $\theta = 0.525$ from something slightly higher. – daniel Nov 6 '12 at 23:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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