

A307422


End squares for a trapped knight moving on a diagonally numbered 2D board where the knight starts from square n.


1



1378, 66, 561, 406, 2701, 1, 78, 15, 561, 78, 120, 1378, 36, 36, 435, 66, 2628, 1275, 78, 378, 190, 1326, 136, 300, 15, 325, 3570, 1, 171, 231, 780, 595, 21, 28, 561, 276, 120, 28, 28, 496, 435, 1, 153, 171, 2415, 28, 496, 300, 2850, 55, 15, 465, 1431
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

For a knight (a 2 X 1 leaper) moving on a diagonally numbered 2D board to the lowestnumbered available square at each step (see A316588), a(n) is the number of the square at which the knight is trapped if it starts from square n. '1' in the sequence indicates no ending square, i.e., the knight's path is unbounded and it leaps forever. Unlike the spirally number board which has a finite list of end square values (see A306291), the diagonally numbered board displays an infinite list of end squares and an infinite number of unbounded paths. Also up to starting squares of 10 million there are only 8 end squares which are not on the left edge of the board.
Unlike the behavior of a knight on a spirally numbered board, this sequence has knight paths which are unbounded, having no ending square. This is due to the knight's path creating linear sequences of visited squares which cannot be crossed by the knight when it revisits the same area of the board. This forces it to follow paths farther and farther from the origin as it moves back and forth between the board's two edges (see link images). The data show that starting square 6, and every 4th square down the left edge of the board from 6, will form such paths and thus be unbounded. These values, u(t), are 6, 28, 66, 120, 190, ..., which can be written as u(t) = 8*t^2  2*t, for all t >= 1. In addition there is one other starting square, 42, which shows similar behavior, although the repetitive pattern the knight's path forms is slightly different.
The above unbounded path starting squares of the form u(t) lead to the presence of paths whose starting square is just one leap away from these squares. But as there is now one extra visited point away from the left edge of the board as the (otherwise unbounded) repetitive path moves outward and over the starting square, the pattern is interrupted; this leads to its eventually being trapped on the left edge, but in a predictable manner based on the value of the initial starting square. The data show that there are three groups of such starting squares, each group having a square u(t) as its second visited square, and each group having a different path to being trapped once the path passes the starting square. These starting and ending squares can be fitted with a quadratic equation; see the example table below. The upshot of this is that there is an ending square associated with each of the unbounded u(t) starting squares, implying there is an infinite list of ending squares whose value grows arbitrarily large with the associated u(t).
The vast majority of all knight paths starting from any square end by being trapped on the left edge of the board: a(1) = 1378 is the first example. The squares 28, 210, 231, 3655 are the dominant end squares: together they trap about 66% of all bounded knight paths. These squares trap the many paths that initially move diagonally straight toward the top edge of the board, then toward the origin before moving back out. Likewise, the squares 69751, 96580, 208981 trap similar paths along the left edge; together these trap about 22% of all bounded paths. On the other hand, data from all starting squares up to 10 million shows leftedge squares which only have one path ending on them; squares 91, 351, 11325, 15225 are examples. The same data also show a few squares on the left edge on which no paths end; 14535 and 49770 are the first two such squares (for values >= 15). It is unknown if these squares never act as end squares or if paths with very large starting squares eventually end on them. Starting squares that lead to paths that initially approach near the origin or the left edge of the board almost always lead to ending squares that are scattered fairly uniformly along all other squares on the left edge of the board. The first few diagonals of the board near the origin never act as ending squares; square 15 was the smallest ending square found, first reached by starting square 8.
Only eight other end squares were found that are not on the left edge of the board. Five of these (with values 5299, 9487, 50254, 208320, 486688) seem to be unique end squares for only one or two starting squares, while the remaining three (with values 4772, 45736, 194996) form the end square for different infinite lists of starting squares; all are from paths initially moving on straight lines toward the origin but which are eventually very close to the end square. In fact, the first member of each of the three infinite lists is a square that also acts as one of the eight blocking squares for the eventual end square. These three lists are also definable by a quadratic. It is unknown if more than these eight nonleftedge end squares exist, although it is plausible that this is the entire list.


LINKS

Table of n, a(n) for n=1..53.
Scott R. Shannon, Path for starting square 780. This is starting square u(10)=780 and thus an unbounded knight path. This shows how the path forms a repetitive and impenetrable wall of visited points as it moves outwards. Note how the position of the starting square (shown in green) is such that it leaves the path's repetitive pattern unaffected as it moves outward from the origin past the starting square. This is only true for every 4th starting square down the lefthand edge of the board.
Scott R. Shannon, Path for starting square 42. This is the only starting square not given by u(t) leading to an unbounded knight path. Note how the position of the starting square is such that it does not interrupt the repetitive pattern of the outward moving knight path, although the resulting pattern is slightly different from a(10) above, and from all other similar unbounded paths.
Scott R. Shannon, Path for start squareing 4011. This path ends at 231  one of the 4 dominant end squares. Square 4011 and all similar starting squares that lead to paths that move to the top edge of the board will follow a similar pattern and all end on one of the squares 28, 210, 231 or 3655.
Scott R. Shannon, Path for starting square 8. This square leads to the first path to be trapped on square 15  the smallest possible end square.
Scott R. Shannon, Path for start square 3080. This is start value = ps(5) = 3080 and has an end square pe(5) = 7381 (shown in red, with blocked squares in blue). Note how the repetitive pattern is broken when the path crosses the starting square as it moves away from the origin, causing the path to become more randomized and eventually trapped.
Scott R. Shannon, Path for starting square 2228. This path ends on square 5299  the first of the five singular nonleftedge ending squares. As the starting square is closer to the origin than the eventual end square, and no other starting points farther out were found that end on 5299, it is probable that the 2228 to 5299 end square path is unique.
Scott R. Shannon, Path for starting square 8953. This is n(12) = 8953, ending on square 4772. All paths that are trapped on square 4772 will have starting squares along the straight line seen in this image, pointing down and right and passing next to the end square itself. The other two end squares 45736 and 194996 show similar behavior.
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019)


EXAMPLE

a(1) = 1378 (see A316588).
The table below shows the starting square to end square mapping  either a single square or a quadratic equation for all valid values, and if the end square(s) are on the left edge of the board. For all quadratics, t >= 1. This is from data for all starting squares up to 10 million.
++
Start  End  Left
square  square  Edge
++
42  NA (unbounded)  
8*t^22*t = u(t)  NA (unbounded)  
++
2228  5299  No
3569  9487  No
27256  50254  No
187573  208320  No
191268, 200657  486688  No
++
9*t^2/2+ 589*t/2+4771 = n(t)  4772  No
9*t^2/2+1813*t/2+45735  45736  No
9*t^2/2+3745*t/2+194995  194996  No
++
72*t^2+222*t+170 = ps(t)  72*t^2+738*t+1891 = pe(t)  Yes
72*t^2+270*t+252  72*t^2+786*t+2145  Yes
72*t^2+318*t+350  72*t^2+666*t+1540  Yes
++
All other  >= 15, of form  Yes
squares  t^2/2+9*t/2+10 
++
For 'All other squares' about 88% of all paths end on one of the squares 28, 210, 231, 3655, 69751, 96580, 208981. Note that some leftedge squares, for example, 14535, currently have no known starting square which leads to a path ending on them.


CROSSREFS

Cf. A316588, A306291.
Sequence in context: A283231 A283790 A323815 * A256627 A260368 A323814
Adjacent sequences: A307419 A307420 A307421 * A307423 A307424 A307425


KEYWORD

sign


AUTHOR

Scott R. Shannon, Apr 08 2019


STATUS

approved



