MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

I wonder what is the expected behavior of this process?


$f^2_{\mathrm{next}}(n) =$ the next prime after $n^2$.

$g_{\mathrm{sqrt}}(n) = \lfloor \sqrt{n} \rfloor$.

Now iterate as follows, with $n = n_0$:

\begin{eqnarray} n &=& f^2_{\mathrm{next}}(n)\\ n &=& g_{\mathrm{sqrt}}(n)\\ n &=& n \pm 1 \;, \end{eqnarray} where $n$ is augmented in the last equation by $\{-1,1\}$ with equal probability.

So, for $n_0=20$, $f^2_{\mathrm{next}}(20)$ is $401$, the next prime after $20^2$, and then $\lfloor \sqrt{401} \rfloor = 20$. But then, the random $\pm 1$ leads to $\lfloor \sqrt{401} \rfloor -1 = 19$, which leads to $f^2_{\mathrm{next}}(19)=$ the next prime after $361$, which is $367$. Etc. So in one random sequence, we see development like this:

So there is a push-forward toward the next prime by $f^2_{\mathrm{next}}(n)$, counterbalanced by a fall-backward via the floor-function in $g_{\mathrm{sqrt}}(n)$, and confused by the $\pm 1$.

Q. What is the ultimate behavior of this sequence for a given $n_0$?

share|cite|improve this question
Legendre conjectured that there is always a prime between $n^2$ and $(n+1)^2$, and this is generally believed to be true. Assuming this, for any $n$, $g(f(n))=n$, so you're just looking at a random walk. – rlo May 3 '14 at 23:15
@rlo: If you make your comment an answer, I will accept it. Thanks! – Joseph O'Rourke May 4 '14 at 9:00
up vote 5 down vote accepted

As requested, I am making my comment into an answer.

It is a conjecture of Legendre that there is always a prime between $n^2$ and $(n+1)^2$. According to Wikipedia, this has been checked for $n$ up to $10^{18}$, and it would follow from standard conjectures about the distribution of gaps between primes. In particular, Legendre's conjecture is roughly equivalent to knowing that $p_{n+1}-p_n \leq 2 \sqrt{p_n}$ for all $n$. The best results we have toward this are due to Baker, Harman, and Pintz, who have shown that $p_{n+1}-p_n \ll p_n^{0.525}$, and it's a conjecture of Cramer that $p_{n+1}-p_n \ll \log^2 p_n$ for all $n$ and that this is sharp (i.e., the limsup of the ratio exists and is positive).

At any rate, assume Legendre's conjecture is true. We then have, for any $n\geq 1$, that $g_{\mathrm{sqrt}}(f^2_\mathrm{next}(n))=n$, and we also visibly have $g_{\mathrm{sqrt}}(f^2_{\mathrm{next}}(0))=1$. Thus, everything interesting is happening with the $\pm 1$ factor in the final step of the iteration, and so we're just looking at a random walk that is not permitted to go below 0.

share|cite|improve this answer
Thanks! This is beautifully clear! – Joseph O'Rourke May 4 '14 at 20:51

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.