A047708 - cp's OEIS frontend

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

Offset: 0

N. J. A. Sloane

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.
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 were 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 to be 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.
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.
Howard A. Landman and Tom Ferguson showed that this is a permutation of the integers at the Jul 24-28 2000 MSRI workshop on combinatorial games.
W. A. Wythoff, "A Modification of the Game of Nim". Nieuw Arch. Wiskunde 8, 199-202, 1907/1909.

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), 135-143. [Annotated scanned copy]
A. Dress, A. Flammenkamp and N. Pink, Additive periodicity of the Sprague-Grundy function of certain Nim games, Adv. Appl. Math., 22, pp. 249-270 (1999).
Rémy Sigrist, PARI program for A047708
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.

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 *)

PARI
```
See Links section.
```

More terms from Howard A. Landman

cp's OEIS Frontend

A047708 Diagonal of Sprague-Grundy function for Wyt Queens (Wythoff's game).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions