cp's OEIS Frontend

Consider a game of "take away" where at each turn a player is presented with an integer. The valid moves are to subtract a nonzero perfect square less than or equal to the starting number to generate the number that will be given to your opponent. The person who is given 0 loses the game. The winner's goal is to win in as few moves as possible, and the loser wants to force the winner to take as many moves as possible. a(n) is the length of the game with starting number n and perfect play by both players.

The optimal strategy in the game is a minimax strategy as follows: Given a starting number n, take away all squares less than n and determine whether playing any of those moves leaves your opponent with a "losing" number. If so, choose the move that leaves your opponent with a loss in the smallest number of moves assuming both of continue with this strategy. If you cannot leave your opponent with a "losing" number, then choose the move that maximizes the number of moves your opponent must take to win assuming both of you continue with this strategy. By applying this strategy recursively with a base case of "the player with 0 as their start loses in 0 moves," a game length for any possible starting position may be determined.