A377015 Squares visited by a knight moving on a square-spiral numbered board where the knight moves to a square which has been previously visited the fewest number of times. If two or more such squares exist the smallest numbered square is chosen.

1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 29, 32, 15, 12, 27, 24, 45, 20, 23, 44, 41, 18, 35, 38, 19, 16, 33, 30, 53, 26, 47, 22, 43, 70, 21, 40, 17, 34, 13, 28, 25, 46, 75, 42, 69, 104, 37, 62, 95, 58, 55, 86, 51, 48, 77, 114, 73, 108, 151, 68, 103, 64, 67, 36, 39, 66, 63, 96, 59, 56, 87, 52, 49, 78, 115, 74, 71, 106, 149, 102, 99, 140, 61, 94, 31, 54, 85, 50

Offset: 1

Author

Scott R. Shannon, Nov 09 2024

Keywords

• nonn
• look

Comments

Unlike similar sequences, e.g. A316667, A362027, A326922, in this variation the knight is never trapped as it can always move to the square which has been previously visited the fewest times, or if two or more surrounding squares exist with the same smallest previous visit count, then it can move to the smallest numbered square of these options.

The first 2016 terms are the same as A316667. In that sequence the path now ends, but here, as the knight is now surrounded by eight squares that have all been visited once, it now chooses the smallest numbered available square, 1733 in this case. This eventually leads it back toward the origin where it revisits the 1 starting square at a(2039). From here it once again chooses the surrounding square with the fewest previous visits, so it begins a new path, but it will avoid the path it previously took back to the origin since those squares will have two previous visits.

The above pattern repeats, causing the knight to go on various excursions of generally increasing length before it revisits the origin - see A377928 for the indices where a(n) = 1. The knight eventually tours paths of increasing complexity, in general moving along distorted loops which are defined by the previous visit count, with straight path lines between these loops. See the attached images.

Interestingly some of the paths between origin visits are identical; for example the path between the 2nd and 3rd visits to the origin is the same as that between the 32nd and 33rd visits. Likewise those between the 5th-6th and 23rd-24th, and 37th-38th and 40th-41st are the same.

Examples

			The board is numbered with the square spiral:
.
  17--16--15--14--13   .
   |               |   .
  18   5---4---3  12   29
   |   |       |   |   |
  19   6   1---2  11   28
   |   |           |   |
  20   7---8---9--10   27
   |                   |
  21--22--23--24--25--26
.
a(1) = 1, the default starting square.
a(2) = 10 as all eight surrounding available squares, 10, 12, 14, 16, 18, 20, 22, 24 have zero previous visits, so it chooses the smallest number of those, namely 10.
a(3) = 3 as there are seven available squares that have zero previous visits, and of those 3 is the smallest number. Note the 1 square is not considered as that has one previous visit which is more than the other seven squares.
a(2017) = 1733 as all eight surrounding available squares have been visit once, so it chooses the smallest number of those, namely 1733. This is the first term to differ from A316667.
		

Links

• Scott R. Shannon, Table of n, a(n) for n = 1..20000
• Scott R. Shannon, Image of the first 100000 terms.
• Scott R. Shannon, Image of the path between the first and second visit to the origin. In this and similar images, the steps are colored white, grey, red, orange, yellow, green, blue, indigo, and violet across the entire path to show their relative ordering. This image is the same as in A316667 except for the additional final steps, colored violet, back to the origin starting at a(2017). Also show as red circles are the visited squares whose eight available neighbours all have the same previous visit count.
• Scott R. Shannon, Image of the path between the second and third visits to the origin.
• Scott R. Shannon, Image of the path between the third and fourth visits to the origin. This shows the path beginning to get more complex - the knight travels along different loops of squares during different parts of its walk, moving between loops via generally straight line paths.
• Scott R. Shannon, Image of the path between the sixth and seventh visits to the origin.
• Scott R. Shannon, Image of the path between the eighth and ninth visits to the origin
• Scott R. Shannon, Image of the path between the twelfth and thirteenth visits to the origin.
• Scott R. Shannon, Image of the path between the twenty-third and twenty-fourth visits to the origin. This is identical to the path between the fifth and sixth visits.
• Scott R. Shannon, Image of the path between the twenty-ninth and thirtieth visits to the origin.

Crossrefs

Cf. A377928, A316667, A362027, A343678, A358278, A358150, A328929, A328909.