# Walking to infinity on the primes: The prime-spiral moat problem

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).  • quick question: stepping back is not allowed? – sleepless in beantown Sep 8 '10 at 3:14
• @sleepless: I consider "stepping back" as permitted. And I allowed that in the above computation. But because I only looked at a portion of the spiral, it turns out that 2357 is reachable with $d=4$ but that requires backward steps from portions of the spiral further out. I'll recompute... – Joseph O'Rourke Sep 8 '10 at 12:37
• An interesting generalization: Consider a d-island to be a set of those primes that are reachable from one another by a set of steps of length at most d. How many 3-islands are at distance r from the origin? How many 4-islands? The pictures suggest sublinear growth, a.k.a less than r such islands for either value of d. Gerhard "Ask Me About System Design" Paseman, 2010.09.08 – Gerhard Paseman Sep 8 '10 at 15:09
• @Gerhard: Interesting question! Incidentally, to gauge $r$ in the images: the left image coordinates run $\pm 75$, the right image coordinates $\pm 100$. – Joseph O'Rourke Sep 8 '10 at 17:00

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.
• While your conjecture implies that there is a prime every $d$ revolution, where $d$ is the bounded distance. This is weaker but not any easier as I describe above. – Gjergji Zaimi Sep 6 '10 at 18:17
• Yes, I see; nice analysis! I wonder now what is the largest width of a known spiral moat, the analog of the $\sqrt{26}$ and $\sqrt{36}$ bounds for Gaussian primes... – Joseph O'Rourke Sep 6 '10 at 18:29