login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A047708 Diagonal of Sprague-Grundy 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+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 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 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.

Wythoff, W. A. ``A Modification of the Game of Nim.'' Nieuw Arch. Wiskunde 8, 199-202, 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), 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, p. 249-270 (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 P-positions of the game, where the previous player has won).

Cf. A048850.

Sequence in context: A244647 A324037 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 14 17:55 EST 2019. Contains 329979 sequences. (Running on oeis4.)