A014586 Nim-Grundy function for Take-a-Square (or Subtract-a-Square) game.

0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 3, 2, 3, 4, 5, 3, 2, 3, 4, 0, 1, 2, 3, 2, 0, 1, 2, 3, 2, 0, 1, 2, 3, 2, 3, 4, 5, 0, 1, 3, 4, 5, 0, 1, 3, 4, 5, 0, 1, 3, 0, 1, 0, 1, 2, 4, 3, 0, 1, 5, 6, 2, 3, 4, 5, 6, 2, 3, 4, 5, 0, 1, 6, 3, 2, 4, 2, 6, 4, 5, 0, 1, 6, 4

Offset: 0

Author

Achim Flammenkamp

Keywords

• nonn

Comments

Concerning the January 1997 dissertation of Achim Flammenkamp, his home page (currently http://wwwhomes.uni-bielefeld.de/cgi-bin/cgiwrap/achim/index.cgi) has the link shown below, and a comment that a book was published in July 1997 by Hans-Jacobs-Verlag, Lage, Germany with the title Lange Perioden in Subtraktions-Spielen (ISBN 3-932136-10-1). This is an enlarged study (more than 200 pages) of his dissertation. - N. J. A. Sloane, Jul 25 2019

References

• R. K. Guy, Unsolved Problems in Number Theory, E26.
• W. W. Rouse Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 12th Edition.

Links

• Eric M. Schmidt, Table of n, a(n) for n = 0..10000 (corrected by _Eric M. Schmidt_, Apr 23 2019)
• David Eppstein, Faster Evaluation of Subtraction Games, Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), Leibniz International Proceedings in Informatics, arXiv:1804.06515 [cs.DS], 2018.
• Achim Flammenkamp, Lange Perioden in Subtraktions-Spielen, Dissertation, Dept. Math., University of Bielefeld, Germany.
• Sean A. Irvine, Java program (github)
• Wikipedia, Sprague-Grundy theorem

Crossrefs

Cf. A030193, A014587-A014589, A297963.

Programs

Sage

def A014586_list(max) :
    res = []
    for i in range(max+1) :
        moves = list({res[i-r^2] for r in range(1, isqrt(i)+1)})
        moves.sort()
        k = len(moves)
        mex = next((j for j in range(k) if moves[j] != j), k)
        res.append(mex)
    return res
A014586_list(100)
# Eric M. Schmidt, Jul 20 2013, corrected Eric M. Schmidt, Apr 23 2019

Formula

a(n) = 0 iff n belongs to A030193. - Rémy Sigrist, May 30 2019