It is an unsolved problem to decide if it is possible to "walk to infinity" from the origin
with bounded-length steps, each touching a Gaussian prime as a stepping stone.
The paper by Ellen Gethner, Stan Wagon, and Brian Wick,
"A Stroll through the Gaussian Primes"
(American Mathematical Monthly, 105: 327-337 (1998))
discusses this Gaussian moat problem and proves that steps of length $< \sqrt{26}$ are
insufficient. Their result was improved to $\sqrt{36}$ in 2005.
My question is:
Is the analogous question easier for the
prime spiral (a.k.a. Ulam spiral)—Can one walk to infinity using bounded-length steps
touching only the spiral coordinates of primes?
What little I know of prime gaps
suggest that should be easier to walk to infinity.
For example, the first gap of 500 does not occur until about $10^{12}$
(more precisely, 499 and 303,371,455,241).
I ask this primarily out of curiosity, and have tagged it 'recreational.'
Edit1. In light of Gjergji's remarks below, I have tagged this as an open problem.
Edit2.
Just for fun, I computed which primes are reachable on a small portion of the spiral,
for step distances $d \le 3$ (left below) and $d \le 4$ (right below);
red=reached, blue=not reached.
The former does not reach 83, the 23rd prime blue dot barely discernable at spiral coordinates (5,-3);
the latter does not reach 5087, the 680th prime blue dot at
spiral coordinates (36,10).
Best Answer
I don't know if any of the probabilistic or percolation models related to the Gaussian (Eisenstein etc.) prime walks have analogues for the problem you suggest. However note that if such an infinite walk was possible it would imply that the gap between successive primes would be $O(\sqrt{p})$, i.e. it is a (slightly weaker) form of Legendre's conjecture. Also note that this is stronger than the bound on prime gaps implied by the Riemann hypothesis which is $O(\sqrt{p}\log p)$, so no, the problem you suggest is not any easier than the other conjectures about patterns of primes.