A square-squareroot integer race sequence involving primes

Question

I wonder what is the expected behavior of this process?

Let

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

Answer 1

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.