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
Keywords
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
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
Comments