OFFSET
1,3
COMMENTS
Also (conjectured) the "winner" or largest remaining number in the following game:
An n X n board is initialized with n^2 chess kings, numbered in raster order. The kings retain their labels after they move. They take turns moving; after king "n^2" moves, king 1 gets to move again.
If a king has already been captured, or has no captures available to it, it passes its turn. On each turn, a king captures the highest-labeled king available. Play continues until no remaining king can capture. The winner is the highest-numbered king remaining. - Allan C. Wechsler, May 01 2020
LINKS
Index entries for linear recurrences with constant coefficients, signature (1,1,-1,1,-1,-1,1).
FORMULA
From Colin Barker, May 06 2020: (Start)
G.f.: x*(1 + x^2 - x^3 + 10*x^4 + 19*x^5 - 12*x^6 + 7*x^7 - 9*x^8 - 9*x^9 + 9*x^10) / ((1 - x)^3*(1 + x)^2*(1 + x^2)).
a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-4) - a(n-5) - a(n-6) + a(n-7) for n>11.
(End)
EXAMPLE
For n=3 we get the following steps:
1-2-3 0-2-3 0-0-3 0-0-0 0-0-0 0-0-0 0-0-0 0-0-0 0-0-0
4-5-6 -> 4-1-6 -> 4-1-2 -> 4-1-3 -> 0-1-3 -> 0-1-3 -> 0-1-3 -> 0-0-3 -> 0-0-0
7-8-9 7-8-9 7-8-9 7-8-9 7-4-9 0-7-9 0-9-0 0-1-0 0-3-0
Therefore a(3)=3, the highest remaining number.
PROG
(PARI) kings_battle(n)={my( N=n^2, K=[1..N] /*position of king i*/, board=K /* king on field i */, i=N, coord(F)=divrem(F-1, n)+[1, 1]~, done); until( done, my( last=i ); until( i == last && done = 1 /*tried all kings*/, K[ i = i%N+1 ] || next /*already taken*/; my( xy=coord(K[i]), m=0); /* see whether this king can take any other one */ forvec( d=vectorv(2, i, [-(xy[i]>1), xy[i]<n]), d && board[ K[i] + [n, 1]*d ]>m && m = board[ K[i] + [n, 1]*d ] ); m || next; /* we can take king m */; board[ K[i] ] = 0/*empty*/; K[i] = K[m]; K[m]=0/*dead*/; board[ K[i]] = i; next(2))); i=vecmax(board); [i, coord(K[i]), board] } \\ for illustration
(PARI) apply( A334559(n)={if(bittest(n, 0), if(n>1, (n-1)^2-1, 1), n==4, 2, n^2-5+bitand(n, 2))}, [1..66]) \\ M. F. Hasler, May 22 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
Ali Sada and M. F. Hasler, May 06 2020
STATUS
approved