# g is defined as a game (set of games), MAX is the maximum possible Sprague-Grundy value.
define SG(g):
  # Make a set of sprague-grundy values 
  seen = new boolean[MAX+1]
  for x in g:
    # It is important to also check if SG(x) fits inside of the bounds of the array,
    # And to ignore it if it does not.
    seen[SG(x)]=true
  curr = 0
  while seen[curr]:
    curr += 1
  return curr

SG = new int[N+1]
# In this instance of this game, since the stack size always decreases,
# 0 cannot have any moves, and is thus 0 Sprague-Grundy.
SG[0] = 0
for g in 1..N:
  # the number of moves, one of the bounds on the SG, cannot exceed the stack size, as it must decrease.
  seen = new boolean[g]
  for x in S:
    if g >= x:
      seen[SG[g-x]] = true
  curr = 0
  while seen[curr]:
    curr += 1
  SG[g] = curr

Something to quickly work through with this sort of game, is to try to calculate the function for some small values, and look for a pattern. Say someone brute forced the SG function for k = 4, the first 20 values look like:

0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4

There's a really strong pattern here! If P_n is defined as a pile of size n in this game, . This can be proven by strong induction.

This game is harder to wrap one's head around, but since we're given the Sprague-Grundy function, we just need to prove the function holds. What we need to prove is that every number x < 2^k - 2 can be written as a xor of j ≤ k - 1 different stacks of size at most k - 1. This can be done by noticing that x can be written as a binary number with at most k - 2 ones, and we can then construct the stacks from the based on which ones are present in the binary representation.

The reason I recommended to first deal with the odd version of the game is that odd games can only produce odd games.

Note that since dividing an odd pile into an odd number of piles creates an odd number of equivalent games, we take the repeated XOR an odd number of times, so the odd case is equivalent to allowing one to take a pile, and decrease its size to any proper divisor of the pile.

Notice then, that every move in that game decreases the count of prime factors of the size by at least one, and at most, reduces the number of factors to 0.

The game on any odd n is then just equivalent to a Nim heap with as many stones as there are prime factors in n.

As an example, , .

Now, consider any even number n, then n = 2^ko for some odd number o. Notice that dividing G_n into an even number of piles is a winning move, as the XOR is 0.