

A047708


Diagonal of SpragueGrundy function for Wyt Queens (Wythoff's game).


3



0, 2, 1, 6, 7, 8, 3, 5, 4, 16, 14, 15, 10, 9, 11, 20, 13, 21, 12, 25, 17, 18, 19, 30, 31, 38, 35, 36, 22, 23, 43, 45, 48, 49, 24, 26, 27, 28, 29, 33, 60, 32, 61, 57, 66, 37, 63, 34, 64, 67, 40, 39, 41, 42, 82, 44, 74, 79, 47, 46, 87, 86, 50, 95, 96, 52, 101, 51, 102, 53, 54
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Since Wythoff(m,n) <= m+n, Wythoff(n,n) <= 2n. It is not known whether there is an efficient (linear in log(m)+log(n)) strategy to compute Wythoff(m,n). Each single row is "easy" in the sense that a+nWythoff(a,n) is eventually periodic.  Howard A. Landman.
Inverse of sequence A048850 considered as a permutation of the nonnegative integers.  Howard A. Landman, Sep 25 2001
Comments from Howard A. Landman, Nov 24 2007 (Start): It is impossible for any integer to appear twice in this sequence because of the way it is constructed. Thus to prove that it is a permutation of the integers, we need only show that every value g appears at least once.
Suppose this was not true; then there must be some g such that for any value of n, G(n,n) is not = g. Since G(n,n) is defined as the smallest number not found as a G(k,n), G(n,k), or G(k,k) for k < n, this can only happen in one of 2 ways; either there is a number g' smaller than g which is chosen (this can occur at most g times) or g already appears as both G(n,k) and G(k,n) for some k < n (because G(n,k) = G(k,n)) (this can happen at most n/2 times).
Thus we have n <= n/2 + g, or n <= 2g; if g has not appeared within the first 2g terms we have a contradiction. Therefore not only must every integer g appear in the sequence, but it must appear within the first 2g terms (and no sooner than term g/2, since G(n,n) <= 2n). Conversely, this also proves that n/2 <= A(n) = G(n,n) <= 2n. (End)


REFERENCES

E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 76.
Howard A. Landman, "A Simple FSMBased Proof of the Additive Periodicity of the SpragueGrundy Function of Wythoff's Game", in R. Nowakowski (ed.), More Games of No Chance.
Howard A. Landman and Tom Ferguson showed that this is a permutation of the integers at the Jul 2428 2000 MSRI workshop on combinatorial games.
Wythoff, W. A. ``A Modification of the Game of Nim.'' Nieuw Arch. Wiskunde 8, 199202, 1907/1909.


LINKS

Rémy Sigrist, Table of n, a(n) for n = 0..4999
H. S. M. Coxeter, The Golden Section, Phyllotaxis and Wythoff's Game, Scripta Math. 19 (1953), 135143. [Annotated scanned copy]
A. Dress, A. Flammenkamp and N. Pink, Additive periodicity of the SpragueGrundy function of certain Nim games, Adv. Appl. Math., 22, p. 249270 (1999).
Rémy Sigrist, PARI program for A047708
Index entries for sequences that are permutations of the natural numbers


MATHEMATICA

mex[list_] := mex[list] = Min[Complement[Range[0, Length[list]], list]];
move[Wnim, {a_, b_}] := move[Wnim, {a, b}] =
Union[Table[{i, b}, {i, 0, a  1}], Table[{a, i}, {i, 0, b  1}],
Table[{a  i, b  i}, {i, 1, Min[a, b]}]];
SpragueGrundy[game_, list_] := SpragueGrundy[game, list] =
mex[SpragueGrundy[game, #] & /@ move[game, list]];
Table[SpragueGrundy[Wnim, {i, i}], {i, 0, 64}] (* Birkas Gyorgy, Apr 19 2011 *)


PROG

(PARI) See Links section.


CROSSREFS

Main diagonal of square array in A004481. Sequences A000201 and A001950 give the m and n coordinates of the zeros of Wythoff (i.e. the Ppositions of the game, where the previous player has won).
Cf. A048850.
Sequence in context: A196554 A244647 A160348 * A256277 A252746 A182883
Adjacent sequences: A047705 A047706 A047707 * A047709 A047710 A047711


KEYWORD

nonn,easy,nice


AUTHOR

N. J. A. Sloane


EXTENSIONS

More terms from Howard A. Landman


STATUS

approved



