A358339 Array read by antidiagonals upwards: A(n,k) is the number of nonequivalent positions in the KRvK endgame on an n X n chessboard with DTM (distance to mate) k, n >= 3, k >= 0.

2, 4, 5, 3, 15, 9, 5, 10, 36, 13, 9, 51, 21, 70, 20, 5, 30, 122, 36, 120, 27, 4, 40, 59, 231, 55, 189, 35, 0, 26, 97, 101, 384, 78, 280, 44, 0, 30, 39, 181, 165, 587, 105, 396, 54, 0, 31, 87, 53, 311, 246, 846, 136, 540, 65, 0, 22, 79, 134, 67, 484, 356, 1167, 171, 715, 77

Offset

3,1

Comments

DTM (distance to mate) is measured in ply (half-moves), equivalence is under action of the square's symmetry group (D_4), however colors can't be swapped because one side always has a rook.

A225552(n) is the maximum value of k such that A(n,k)!=0, divided by 2 because it's in moves instead of ply (though each column seems to terminate at an even (losing) k, so perhaps no information is lost).

In each column, there are n-2 positions counted (in which the king without the rook is to move) that are orphans (with no predecessors), each represented by a horizontally-shifted version of the piece configuration (Ka1 - Kc2 Rc1) (in which the rook is blocked from having been moved downwards (to cause the check) by its king, that could not have exited from in front without having been adjacent to the king to move). Each one's DTM corresponds with the distance of the king to move from the corner in the opposite direction from the other king, DTM is 4 when on a1, 12 when on b1, 18 when on c1, 22 when on d1, 28 when on e1, and increasing by 2 for all thereafter.

Positions with the side with the king to move at a1, its rook at b1 and the opponent king at (ceiling(n/2),ceiling(n/2)) seem to be wins in 4*n - 6 + 2*floor((n+1)/2) - 2*floor(n/6).

.

For fixed values of n, all values A(n,k) with odd k (winning positions) seem to exceed A(n,k-1) and A(n,k+1) (losing positions) until a threshold value, beyond which this relationship inverts.

For all k, A(n,k)/Sum_{k>=0}(A(n,k)) is o(1) over n (for n>=A225552^(-1)(2*k)), so there is no k such that the polynomial eventually describing A(n,k) is of degree 6, and for all j, Sum_{k=0..j}(A(n,k)) is o(Sum_{k>=0}(A(n,k))).

For each k, there exists a polynomial eventually describing A(n,k) over n, though there can be arbitrarily many leading zero terms so it can take arbitrarily long to do so. Note that it is not necessarily an upper bound.

All polynomials for k >= 7 are quadratic.

.

Conjecture 1: If A(n+1,k) is nonzero, it is always greater than A(n,k).

Conjecture 2: As the increments to A225552 become periodic for n>24, so too do the differences between successive polynomials over n for each k>108, and for all j, Sum_{k=2*A225552(n)-j..2*A225552(n)}(A(n,k)) is o(Sum_{k>=0}(A(n,k))) (the same equation from the opposite side).

Conjecture 3: (Begin)

Note that Sum_{k>=0}(A(n,k)-A(n-1,k)) ~ 3*n^5/2. (See FORMULA for the exact form.)

For all n, assuming conjecture 2, because the polynomials provide upper bounds and all are of degree <=5, it is necessary for the sum of all nonzero A(n,k)'s polynomials (for k<=2*A225552(n)) to have n^2 coefficients summing to 3*n^4/2.

A225552(n) ~ 7*n/3 (and seems to become periodic for n>24), so the number of elements added with each increment of n is ~ 14/3.

Thus, for n>24, the change of 3/2 to the sum of n^5 coefficients with each increment to n causes each new term's eventual polynomial to have an n^2 term with a coefficient asymptotic to (3/2)/(14/3)*n^2=9*n^2/28.

(End)

Conjecture 4: The function o (defined in the FORMULA section), for each parity of k, contains only polynomials over n (without any terms with coefficients of n%2 or (-1)**n). For all m>=3, there exists a pair of polynomials over n (for even and odd k), such that when o adds them to the output of the k-specific fitting polynomial for n=k-m, the values returned are correct for all k>=5*(m-1). (Works for m=2,3,4.) Equivalently, for all k>10, while A(n,k) can be described exactly by a k-specific polynomial over n for all n>=A052928(k), it can be described exactly by the sum of that and a (2*k-n)-specific polynomial over n (or equivalently, over k) for all n>=k-1-floor(k/5).

Links

Table of n, a(n) for n=3..68.

Vaclav Kotesovec, King and Two Generalised Knights against King, ICGA Journal, Vol. 24, No. 2, pp. 105-107 (2001).

Vaclav Kotesovec, Fairy chess endings on an n x n chessboard, Electronic edition of chess booklets by Vaclav Kotesovec, vol. 8, pp. 360-361 (2013).

Ronald de Man, Bojun Guo, and Niklas Fiekas, KRvK.json, syzygy-tables.info

Formula

Sum_{k>=0}(A(n,2*k)) = (n^6 - 19*n^4 + 27*n^3 + 93*n^2 - 242*n + 112 + (-n^3+7*n^2-18*n+16)*(-1)^n)/8. (losing/checkmated positions)

Sum_{k>=0}(A(n,2*k+1)) = (n-2)*(n-1)*(3*n^4 + 3*n^3 - 22*n^2 + 19*n - 15 + (3-n)*(-1)^n)/24. (winning positions)

Sum_{k>=0}(A(n,k)) = (6*n^6 - 6*n^5 - 82*n^4 + 172*n^3 + 163*n^2 - 643*n + 306 + (2-n)*(4*n^2 - 19*n + 27)*(-1)^n)/24.

Note that for n>=3, there are n+1 nonequivalent positions that are stalemates, each one with the king to move at a1 (under symmetry), 2 with the rook on b2 and its king on c2 or c3, and n-1 with the other at c1 and the rook in one of the squares on the second rank and file >= b.

There are also (n-2)*(4*n^3 + 2*n^2 - 43*n + 31 + (3-n)*(-1)^n)/4 positions in which the rook can be immediately captured (making it unwinnable) that are not included in the sequence, and A357723(n) in the resulting KvK endgame.

The winning positions are those in which the side with the rook is to move, but to get the number in which the side without the rook is to, adding the losing and stalemated positions yields (n-2)*(n^5 + 2*n^4 - 15*n^3 - 3*n^2 + 87*n - 60 - (n^2 - 5*n + 8)*(-1)^n)/8, then adding yields (n-2)*(n-1)*(n^4 + 3*n^3 - 4*n^2 - 3*n - 2 + (2-n)*(-1)^n)/8, so the equations for each side to move both have roots at n=1 and n=2.

In total, there are (n-2)*(n-1)*(6*n^4 + 12*n^3 - 34*n^2 + 10*n - 21 + (-4*n+9)*(-1)^n)/24 nonequivalent positions in the KRvK endgame.

Sum_{k>=0}(A(n,k)-A(n-1,k)) = (18*n^5 - 60*n^4 - 74*n^3 + 429*n^2 - 226*n - 282 + (-4*n^3 + 33*n^2 - 98*n + 102)*(-1)^n)/12.

.

The values of n at which each value of k begins to abide by a polynomial are ((2,1,2,4,6,5,5,6,8,7)[k] if k<10 else (floor(k/2)*2 = A052928(k))). This value can be changed (reduced for k>=10) to ((2,1,1,4,6,5,6,5,7,7,7,8,9,9,11,11,12,13,14,15)[k] if k<20 else k-5) by adding the output of the following function to each polynomial at each value (offsetting only 5-k%2 values):

define o(n,k):

.if k is odd:

..if n=k-2:

...add (n-1)/2-3

..else if n=k-3:

...add n-4

..else if n=k-4:

...add n^2-n-15

..else if n=k-5:

...add 3*n^2-(9*n+23)/2

.else:

..if k-n=1:

...add (n-1)/2-1

..else if n=k-2:

...add n-1

..else if n=k-3:

...add 4*n-15

..else if n=k-4:

...add 8*n-35

..else if n=k-5:

...add (25*n-137)/2

.

A(n, k) = 0 if n<3 or k>2*A225552(n).

The sequence measures distance to mate, as is convention in chess (so A(n,0) counts positions in checkmate), however if kings were to be allowed to be captured, the number of positions after a move into check from a position in checkmate (usually considered illegal) would be

A(n,-1) = (n-1)*(6*n^4 + 22*n^3 - 60*n^2 + 59*n - 24 + (n-2*n^2)*(-1)^n)/24

(note that (n-1)*(4*n + 1 - (-1)^n)/4 of these cases have the rook captured)

A(n, 0) = 0 if n<2 else (n-2)*(n+1)/2 = n^2/2 - n/2 - 1 = A000096(n-2).

A(n, 1) = 0 if n<1 else (n-2)*(n-1)*(n+1)/2 = n^3/2 - n^2 - n/2 + 1 = A077414(n-1).

A(n, 2) = 0 if n<2 else (n-2)*(2*n-3) = 2*n^2 - 7*n + 6 = A014105(n-2).

A(n, 3) = (0,0,0,5)[n] if n<4 else n^3 + 4*n^2 - 26*n + 27 = m^3 - 94*m/3 + 1793/27, where m = n + 4/3.

A(n, 4) = (0,0,0,9,30,59)[n] if n<6 else (2*n^3 - 5*n + 5 + (3-n)*(-1)^(n))/4

A(n, 5) = (0,0,0,5,40)[n] if n<5 else (6*n^3 - 26*n^2 + 84*n - 135 + (7-2*n)*(-1)^n)/4 = 3*m^3/2 + 209*m/18 - 12109/972 + (m/2-37/36)*(-1)^n, where m = n - 13/9.

A(n, 6) = (0,0,0,4,26)[n] if n<5 else 14*n - 31.

A(n, 7) = (0,0,0,0,30, 87)[n] if n<6 else 2*n^2 + 24*n - 82.

A(n, 8) = (0,0,0,0,31, 79,116)[n] if n<7 else 2*n^2 + 14*n - 42 + o().

A(n, 9) = (0,0,0,0,22,174,310)[n] if n<7 else 11*n^2 - 7*n - 41.

A(n,10) = (0,0,0,0,65,178,262)[n] if n<7 else 7*n^2 + 7*n - 40 + o(n,10).

A(n,11) = (0,0,0,0, 7,180,492, 795)[n] if n<8 else 45*n^2/2 - 73*n/2 - 61 + o(n,11).

A(n,12) = (0,0,0,0,25,206,291, 449, 592)[n] if n<9 else 9*n^2 + 7*n - 64 + o(n,12).

A(n,13) = (0,0,0,0, 2,125,461,1002,1418)[n] if n<9 else (53*n^2 - 75*n)/2 - 58 + o(n,13).

A(n,14) = (0,0,0,0, 6,243,397, 552, 683, 805, 939)[n] if n<11 else (7*n^2 + 141*n)/2 - 160 + o(n,14).

A(n,15) = (0,0,0,0, 0, 49,447,1147,2149,2950,3709)[n] if n<11 else (91*n^2 - 205*n)/2 - 44 + o(n,15).

A(n,16) = (0,0,0,0, 0,136,619, 986,1433,1836,2254,2559)[n] if n<12 else (39*n^2 + 47*n)/2 - 134 + o(n,16).

A(n,17) = (0,0,0,0, 0, 19,473,1303,2514,4166,5703,6973,8306)[n] if n<13 else (139*n^2 - 341*n)/2 - 16 + o(n,17).

A(n,18) = (0,0,0,0, 0, 70,698,1207,1712,2376,3075, 3578, 4197, 4690)[n] if n<14 else (49*n^2 + 97*n)/2 - 179 + o(n,18).

A(n,19) = (0,0,0,0, 0, 2,292,1154,2382,4296,6722, 8563,10691,12530,14445)[n] if n<15 else (171*n^2 - 389*n)/2 - 94 + o(n,19).

A(n,20) = (0,0,0,0, 0, 7,782,1515,1985,2624,3532, 4518, 5466, 6308, 7261)[n] if n<15 else 34*n^2 + 42*n - 302 + o(n,20).

A(n,21) = (0,0,0,0, 0, 0, 96,1124,2565,4341,7182,10310,13031,15307,18270,20921)[n] if n<16 else 106*n^2 - 262*n + 6 + o(n,21).

A(n,22) = (0,0,0,0, 0, 0,313,2116,2854,3322,4186, 5212, 6278, 7313, 8479, 9494,10681)[n] if n<17 else 35*n^2 + 106*n - 358 + o(n,22).

A(n,23) = (0,0,0,0, 0, 0, 13, 832,2691,5011,7578,11884,16461,19759,23062,26187,30474,34401)[n] if n<18 else 133*n^2 - 306*n - 194 + o(n,23).

A(n,24) = (0,0,0,0, 0, 0, 45,2002,3597,5172,6558, 7114, 8891,10534,11965,13623,15618,17470,19443)[n] if n<19 else (109*n^2 + 223*n)/2 - 687 + o(n,24).

A(n,25) = (0,0,0,0, 0, 0, 0, 258,2234,5482,9412,13305,20056,25698,30163,33982,39027,43570,49523,55256) if n<20 else (345*n^2 - 931*n)/2 + 60 + o(n,25).

A(n,26) = (0,0,0,0, 0, 0, 0, 773,4194,6209,8937,10557,12341,13901,15940,18224,20672,23119,25666,28471,31426) if n<21 else 75*n^2 + 73*n - 589 + o(n,26).

Example

Array begins (transposed):
 k\n| 3  4    5     6     7     8   9      10   11 ...
----+---------------------------------------------
  0 | 2  5    9    14    20    27   35     44   54
  1 | 4 15   36    70   120   189  280    396  540
  2 | 3 10   21    36    55    78  105    136  171
  3 | 5 51  122   231   384   587  846   1167 1556
  4 | 9 30   59 | 101   165   246  356    487  655
  5 | 5 40 | 97   181   311   484  725   1023 1411
  6 | 4 26 | 39    53    67    81   95    109  123
  7 | 0 30   87 | 134   184   238  296    358  424
  8 | 0 31   79   116   156 | 198  246    298  354
  9 | 0 22  174   310 | 449   607  787    989 1213
 10 | 0 65  178   262   365   471  593 |  730  884
 11 | 0  7  180   492   795  1097 1434 | 1824 2260
...
(where vertical lines denote indexes at which the rows for fixed k begin to abide by polynomials)
The following diagrams are positions counted. Pieces with uppercase letters are next to move.
.
A(3,0)=2:
  |r   |r  |
  |    |  k|
  |K  k|K  |
.
A(3,1)=4:
  | R |R  |k  |k  |
  |   |   |  R|   |
  |K k|K k| K | KR|
.
A(3,2)=3:
  |k r| kr| k |
  |   |   |  r|
  | K | K | K |
.
A(3,3)=5:
  | R |R  |   | k | k |
  |  k|  k|  k|R  |   |
  |K  |K  |KR | K |RK |
.
A(3,4)=9:
  |  r| r |   |  r| r |   |   | rk|r k|
  |   |   |   |  k|  k|  k|  k|   |   |
  |K k|K k|Krk|K  |K  |K r|Kr |K  |K  |
.
A(3,5)=5:
  |   |   |  k|  k|k  |
  | R |R  | R |   | R |
  |K k|K k|K  |KR | K |
.
A(3,6)=4:
  |kr |k  |k  | k |
  |   | r |r  | r |
  | K | K | K | K |

Crossrefs

Nonzero column lengths: A225552, nonequivalent KvK positions: A357723.

Rows k=0..2: A000096(n-2), A077414(n-1), A014105(n-2).

Sequence in context: A118461 A332667 A266408 * A230564 A011174 A123545

Adjacent sequences: A358336 A358337 A358338 * A358340 A358341 A358342

Keyword

nonn,tabl

Author

Nathan L. Skirrow, Nov 10 2022

Status

approved