Tuesday, July 17, 2018

[zbnwixis] 2D Recaman sequence

Modify the Recaman sequence OEIS A005132 to travel between points on a 2D lattice instead of integers on the number line. The jump sizes increase according to the square roots of OEIS A001481, numbers which are the sum of 2 squares.  There are many jumps (usually at least 8) possible: choose the jump to the point that hasn't been previously visited that gets closest to the origin.

What should be done if there are many valid points that are equal distance to the origin?  Some possibilities:

1. Jump to all of them: it's no longer a sequence but a tree.  Actually digraph because two braches could simultaneously jump to the same point.
2. Choose the one that's closest to the previous point.  Break ties by going further back in time.
3. Or farthest.
4. Closest to any previous point.  Break ties by considering the second closest previously visited point, etc.
5. Or farthest.

Incidentally, we could terminate the 1D Recaman sequence when the jump forward or backward are both numbers which have already been visited.  The sequence would terminate before the second 42.  If we want a longer sequence, the jump sizes probably have to grow faster than 1,2,3,...  Maybe skip that jump size?  Then what is the rate of growth of the jump sizes?

Consider using the same termination criterion, terminate if no jumps possible, for branches of the tree in possibilty 1 above.