Moat-Crossing Problem


There are two versions of the moat-crossing problem, one geometric and one algebraic. The geometric moat problems asks for the widest moat Rapunzel can cross to escape if she has only two unit-length boards (and no means to nail or otherwise attach them together). More generally, what is the widest moat which can be crossed using n boards? Matthew Cook has conjectured that the asymptotic solution to this problem is O(n^(1/3)) (Cook 1997).

The algebraic moat-crossing problem asks if it is possible to walk to infinity on the real line using only steps of bounded lengths and steps on the prime numbers. The answer is negative (Gethner et al. 1998). However, the Gaussian moat problem that asks whether it is possible to walk to infinity in the Gaussian integers using the Gaussian primes as stepping stones and taking steps of bounded length is unresolved. Gethner et al. (1998) show that a moat of width sqrt(26) exists.

Explore with Wolfram|Alpha


Cook, M. "Update on the Moat Crossing Problem." E-mail communication, 1997., S. "Moat Crossing Optimization Problem.", E. and Stark, H. M. "Periodic Gaussian Moats." Experiment. Math. 6, 251-254, 1997.Gethner, E.; Wagon, S.; and Wick, B. "A Stroll Through the Gaussian Primes." Amer. Math. Monthly 105, 327-337, 1998.Guy, R. K. Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, 1994.Haugland, J. K. "A Walk on Complex Primes." [Norwegian.] Normat 43, 168-170, 1995.Jordan, J. H. and Rabung, J. R. "A Conjecture of Paul Erdős Concerning Gaussian Primes." Math. Comput. 24, 221-223, 1970.Montgomery, H. Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis. Providence, RI: Amer. Math. Soc., 1994.Vardi, I. "Prime Percolation." Experiment. Math. 7, 275-289, 1998.Wagon, S. Mathematica in Action, 2nd ed. New York: Springer-Verlag, 1999.

Referenced on Wolfram|Alpha

Moat-Crossing Problem

Cite this as:

Weisstein, Eric W. "Moat-Crossing Problem." From MathWorld--A Wolfram Web Resource.

Subject classifications