A338027 Lengths of games in optimal play of "subtract-a-square".

0, 1, 2, 3, 1, 2, 3, 4, 5, 1, 4, 3, 6, 7, 3, 4, 1, 8, 3, 5, 6, 3, 8, 5, 5, 1, 5, 3, 7, 7, 3, 5, 5, 9, 10, 5, 1, 7, 3, 6, 5, 3, 9, 5, 8, 7, 5, 9, 7, 1, 11, 3, 8, 9, 3, 7, 5, 10, 9, 5, 9, 7, 10, 11, 1, 8, 3, 12, 9, 3, 11, 5, 12, 11, 5, 7, 7, 9, 11, 5, 9, 1, 11, 3, 7, 10

Offset

0,3

Comments

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.

Links

Josh Bauer, Table of n, a(n) for n = 0..10000

Josh Bauer, Annotated implementation in python running in O(n^(3/2)) to get the first n terms

Formula

Let S(n) be the set of nonzero perfect squares less than or equal to n. Let E be the set of even numbers.

a(0) = 0;

a(n) = Min_{a(n - s) with s in S(n) and a(n - s) in E} + 1 if there are any values of s in S(n) for which a(n - s) is in E. Otherwise:

a(n) = Max_{a(n - s) with s in S(n)} + 1.

Example

If the starting number is 0, then the starting player loses immediately (in 0 turns), so a(0) = 0. If the starting number is a perfect square, the player can give their opponent a 0 in one move by subtracting the square immediately, thus a(n^2) = 1. If the starting number is 15, the player whose turn it is cannot win unless the other player plays suboptimally. An example optimal game from this point would be: 15 (loser takes away 4), 11 (winner takes away 9), 2 (loser takes away 1), 1 (winner takes away 1), 0 (current player loses). Thus a(15) = 4, a(11) = 3, a(2) = 2, a(1) = 1, and a(0) = 0.

Prog

(Python) # See Bauer link

Crossrefs

A030193 gives all indices at which this sequence has an even value (corresponding to the losing positions).

Sequence in context: A003315 A194107 A071797 * A380356 A025481 A124171

Adjacent sequences: A338024 A338025 A338026 * A338028 A338029 A338030

Keyword

nonn

Author

Josh Bauer, Oct 07 2020

Status

approved