16
$\begingroup$

When exploring the structure of points of the integer lattice whose two coordinates are relatively prime (call these r-prime points),1 I looked at spirals analogous to "Gaussian prime spirals."2 Start at an r-prime point $(a,b)$, walk vertically (North) until you hit another r-prime point, then walk West until another r-prime point is hit, then South, then East, continuing to turn counterclockwise $90^\circ$ at r-prime points until you re-encounter an earlier point, approached from the same direction as last hit, and so fall into a cycle. (The start point is considered approached from its left.) Unlike the Gaussian prime spirals, these "relatively primes spirals" are not generally visually interesting. Many are just $4$-cycles, e.g.: $$ (223, 2), (223, 3), (221, 3), (221, 2) $$ Let me illustrate one more before asking a question. Starting at $(495,2)$ leads to a cycle of length $44$: $$ (495, 2), (495, 4), (493, 4), (493, 3), (494, 3), (494, 5), (493, 5), (493, 4), (495, 4), (495, 7), (494, 7), (494, 5), (496, 5), (496, 7), (495, 7), (495, 4), (497, 4), (497, 5), (496, 5), (496, 3), (497, 3), (497, 4), (495, 4), (495, 2), (497, 2), (497, 3), (496, 3), (496, 1), (497, 1), (497, 2), (495, 2), (495, 1), (496, 1), (496, 3), (494, 3), (494, 1), (495, 1), (495, 2), (493, 2), (493, 1), (494, 1), (494, 3), (493, 3), (493, 2) $$ Here is an illustration of this cycle:


          (495,2)


A natural question is:

Does any start point lead to an infinite path that never cycles?

A candidate infinite path starts at $(5,2)$: $$ (5, 2), (5, 3), (4, 3), (4, 1), (5, 1), (5, 2), (3, 2), (3, 1), (4, 1), (4, 3), (2,3), (2,1), \ldots $$ Here is its first $200$ turns:


          (5,2):200
And here is its first $1000$ turns:
          (5,2):1000
And here is its first $10000$ turns:
          (5,2):10000
I've tracked it out to $10^6$ turns (reaching out to $(87652,87655)$), and still no cycle. So, in addition to the general question above, a more specific question is whether $(5,2)$ ever cycles.

Added animation:


          rprime200.gif



1Arbitrarily long composite anti-diagonals?

2Gaussian prime spirals

$\endgroup$
  • $\begingroup$ What happens when you run the process in reverse starting at $(5,2)$? $\endgroup$ – Will Sawin Dec 28 '16 at 22:10
  • 1
    $\begingroup$ If this path doesn't run forever, it necessarily meets its own tail. My hope is that the tail makes it to negative numbers, and that we can show there is a wall separating negative and positive numbers with only one path through - a path that $(5,2)$ already used. This would show it runs forever. $\endgroup$ – Will Sawin Dec 28 '16 at 22:14
  • $\begingroup$ The backwards direction is West, North, East, South. $\endgroup$ – Will Sawin Dec 28 '16 at 22:15
  • 1
    $\begingroup$ Those interested in primes and spirals may want to check out math.stackexchange.com/questions/2072308/… $\endgroup$ – Gerry Myerson Jan 1 '17 at 14:48
11
$\begingroup$

First note that, in the path, the coordinates are always positive, because whenever any coordinate decreases to $1$ you hit a relatively prime point, turn, hit another relatively prime point, and then the coordinate starts increasing again,

Next consider the following set of posiitions and next directions:

A $(x,y), y>x+1$, any direction

B $(x,x+1)$, North, East, or West

C $(x,x-1)$, North

This set is closed under your operation. The reason is that if you ever leave type A you must be traveling South or East and hit the R-prime point $(x,x+1)$, so you are then traveling East or North, hence be in type B. If you leave type B and travel North or West you return to A, and traveling east you skip the non-R-prime point $(x+1,x+1)$ (note $x$ is at least $1$) and travel straight to $(x+2,x+1)$ and turn North, hence in a point in C. Finally C returns to B in the same way by skipping $(x,x)$ (note $x$ is at least $2$) and turning West.

Because your spiral enters this closed set, it never leaves it and hence never returns to its initial point. Because the flow is reversible, this means it must run forever without repeating.

$\endgroup$
  • 2
    $\begingroup$ This answer is at least as awesome as the question! $\endgroup$ – R. van Dobben de Bruyn Dec 28 '16 at 23:21
  • $\begingroup$ Beautiful argument! It appears (visually) that, not only doesn't the $(5,2)$ spiral close and repeat, but it also seems never to repeat the same "structural units" (however defined) as it walks out above the $y=x$ diagonal. If you also have any remarks on that behavior, I would appreciate your insights. Thanks! $\endgroup$ – Joseph O'Rourke Dec 29 '16 at 3:56
  • $\begingroup$ @JosephO'Rourke I'm not sure I see what you mean. In your "first 1,000 turns" picture, the same (small) structural unit appears near $(20,20)$ and near $(50,50)$. If the sequence were random, we would expect a structural unit of size $n$, whatever that means, to repeat after an exponential-in-$n$ number of steps. Is that what you're seeing? $\endgroup$ – Will Sawin Dec 29 '16 at 7:21
  • $\begingroup$ @JosephO'Rourke In lieu of that, two fun facts I think I can prove: 1. This sequence, when extended backwards in time, is symmetric about the $(x,y)$ axis 2. every other path is closed. $\endgroup$ – Will Sawin Dec 29 '16 at 7:24
  • $\begingroup$ @JosephO'Rourke 1. This is easy to check from the fact that the backwards evolution rule is the forwards evolution rule, flipped around the $x=y$ axis. 2. Check first for paths contained in the sets A, B, C. Observe that, in this set, the only way to get from $y= p-\epsilon$ to $y=p + \epsilon$ for a prime $p$ is by passing vertically through $(p,p)$ - everywhere else you will be stopped by a relatively prime point and turn around. The path starting at $(5,2)$ passes through $(p,p)$ because it is infinite, so no other path can. Then use this symmetry to handle paths in the other octant. $\endgroup$ – Will Sawin Dec 29 '16 at 7:30

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.