OFFSET
1,1
COMMENTS
For a knight (a 2 X 1 leaper) moving on a diagonally numbered 2D board to the lowest-numbered 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 left-edge 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 non-left-edge end squares exist, although it is plausible that this is the entire list.
LINKS
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 left-hand 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 non-left-edge 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^2-2*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 left-edge squares, for example, 14535, currently have no known starting square which leads to a path ending on them.
CROSSREFS
KEYWORD
sign
AUTHOR
Scott R. Shannon, Apr 08 2019
STATUS
approved