A334559 - OEIS

%I #22 Aug 03 2020 01:19:33

%S 1,1,3,2,15,33,35,59,63,97,99,139,143,193,195,251,255,321,323,395,399,

%T 481,483,571,575,673,675,779,783,897,899,1019,1023,1153,1155,1291,

%U 1295,1441,1443,1595,1599,1761,1763,1931,1935,2113,2115,2299,2303,2497,2499

%N a(2n+1) = (2n)^2 - 1, a(4n+2) = (4n+2)^2 - 3, a(4n) = (4n)^2 - 5, except for a(1) = 1, a(4) = 2. (Conjectured outcome of an elimination game, see comments.)

%C Also (conjectured) the "winner" or largest remaining number in the following game:

%C 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.

%C 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

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,-1,1,-1,-1,1).

%F From _Colin Barker_, May 06 2020: (Start)

%F 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)).

%F 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.

%F (End)

%e For n=3 we get the following steps:

%e 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

%e 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

%e 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

%e Therefore a(3)=3, the highest remaining number.

%o (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

%o (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

%K nonn

%O 1,3

%A _Ali Sada_ and _M. F. Hasler_, May 06 2020