0,2

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+n-Wythoff(a,n) is eventually periodic. - Howard A. Landman (howard(AT)polyamory.org).

Inverse of sequence A048850 considered as a permutation of the nonnegative integers. - Howard A. Landman (howard(AT)polyamory.org), Sep 25 2001

Comments from Howard A. Landman (howard(AT)riverrock.org), 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)

E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 76.

Coxeter, H. S. M. ``The Golden Section, Phyllotaxis and Wythoff's Game.'' Scripta Math. 19, 135-143, 1953.

A. Dress, A. Flammenkamp and N. Pink, Additive periodicity of the Sprague-Grundy function of certain Nim games, Adv. Appl. Math., 22, p. 249-270 (1999).

Wythoff, W. A. ``A Modification of the Game of Nim.'' Nieuw Arch. Wiskunde 8, 199-202, 1907/1909.

Howard A. Landman (howard(AT)polyamory.org) and Tom Ferguson showed that this is a permutation of the integers at the Jul 24-28 2000 MSRI workshop on combinatorial games.

Howard A. Landman, "A Simple FSM-Based Proof of the Additive Periodicity of the Sprague-Grundy Function of Wythoff's Game", in R. Nowakowski (ed.), More Games of No Chance.

Index entries for sequences that are permutations of the natural numbers

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 P-positions of the game, where the previous player has won).

Cf. A048850.

Sequence in context: A066752 A059364 A160348 this_sequence A110608 A112007 A113374

Adjacent sequences: A047705 A047706 A047707 this_sequence A047709 A047710 A047711

nonn,easy,nice

N. J. A. Sloane (njas(AT)research.att.com).

More terms from Howard A. Landman (howard(AT)polyamory.org).