OFFSET
0,2
COMMENTS
If there is more than one possible move with the same distance to the origin, the length of the 2nd difference ("acceleration") is minimized, then the length of the 3rd difference is minimized, etc (see example). (The 1st differences always have length sqrt(5), so there is no point in comparing them.) If there is still a tie after comparing the n-th differences (using all previous points on the path), the lexicographically largest point is chosen. This last rule seems never to come into play, except for the very first step.
Backtracking (discarding a candidate move because it inevitably leads to a dead end) is needed for the first time in the 92068th step, in which the step to (62,-158) is discarded because all its neighbors are already visited. Instead the knight moves to (65,-159). (62,-158) is also the position closest to the origin of the positions that are never visited. Among the first 1000000 steps, backtracking is needed 22 times.
The first time the 3rd differences need to be compared is at the 1793rd step (see example). Among the first 1000000 steps, differences of order higher than 3 never need to be compared; 3rd differences are needed 11 times.
LINKS
Pontus von Brömssen, Table of n, a(n) for n = 0..10000
Pontus von Brömssen, Illustration of the first 100 steps.
Pontus von Brömssen, Illustration of the first 20000 steps.
Pontus von Brömssen, Plot of the running winding number of the first 1000000 steps of the path, starting from 0 at the first step.
Pontus von Brömssen, Plot of path, using Plot2.
EXAMPLE
After the 1792nd step the knight is at (20,-10). The positions (18,-9), (19,-8), and (18,-11) with distances sqrt(405), sqrt(425), and sqrt(445) to the origin, respectively, are already visited. Of the remaining candidate points, (21,-8) and (19,-12) are closest to the origin at distance sqrt(505). The positions preceding (20,-10) are (20,-12) and (22,-11). For the candidate (21,-8), the successive differences are as follows:
(20,-12) (22,-11) (20,-10) (21, -8);
( 2, 1) (-2, 1) ( 1, 2);
(-4, 0) ( 3, 1);
( 7, 1).
For the candidate (19,-12) the successive differences are:
(20,-12) (22,-11) (20,-10) (19,-12);
( 2, 1) (-2, 1) (-1, -2);
(-4, 0) ( 1, -3);
( 5, -3).
The 2nd differences (3,1) and (1,-3) both have length sqrt(10), but the third differences (7,1) and (5,-3) have lengths sqrt(50) and sqrt(34), respectively, so the 2nd candidate (19,-12) is preferred. (This is the first time the 3rd differences need to be compared.) To be certain that the point (19,-12) is actually chosen, one should also verify that it is still possible to continue the path indefinitely from the chosen point, which is the case here.
CROSSREFS
KEYWORD
sign,changed
AUTHOR
Pontus von Brömssen, Jun 11 2026
STATUS
approved