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,5

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

Formula

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

Prog

(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

Crossrefs

Cf. A030193, A014587-A014589, A297963.

Sequence in context: A298307 A287002 A119346 * A122924 A133450 A029410

Adjacent sequences: A014583 A014584 A014585 * A014587 A014588 A014589

Keyword

nonn

Author

Achim Flammenkamp

Status

approved