# 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

# x,y,z are the dimensions of the cuboid in this case.
def SG(x,y,z):
  # The upper bound can be determined through experimentation, for this one, 1000 was more than sufficient
  seen = new boolean[<sufficiently large number>] 
  for a in 0..x
    for b in 0..y
      for c in 0..z
        # the sprague-grundy of cutting the 0-indexed cell (a,b,c) is as follows
        # There are 8 games that result, some of which are over.
        seen[ SG(a,b,c)         ^ SG(a,b, z-1-c)    ^
              SG(a,y-1-b,c)     ^ SG(a,y-1-b,z-1-c) ^
              SG(x-1-a,b,c)     ^ SG(x-1-a,b, z-1-c)^
              SG(x-1-a,y-1-b,c) ^ SG(x-1-a,y-1-b,z-1-c)] = True
  mex = 0
  while seen[mex]:
    mex += 1
  return mex

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. Additionally, you should prove that no combination of smaller games can XOR to 2^k - 2, which can be seen from the number of digits 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 = o2^k 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. Now, consider any other move, which must divide n into b piles of size 2^ko / b, for some b that divides o. This is equivalent to turning the pile of size n into a single pile of size 2^ko / b. Thus, we can either move the game to a losing position (SG of 0), or reduce the number of odd prime factors of n. This analysis leads us to the idea that the Sprague-Grundy of a pile with an even number of stones is 1 more than the number of odd prime factors.

We prove inductively on the maximum total number of moves in a game. This is obviously true for a game with no moves remaining, as , and . Let MT(X) represent the maximum number of turns X can take. Note that MT(C(A, B)) = MT(A) + MT(B). Now, if we assume for induction that the theorem is true for all A, B such that together MT(A) + MT(B) < n.

Then, if MT(A) + MT(B) = n, note that Since C(A, B) has at most n turns, MT(C(a, B)) < n, and similar for MT(C(A, b)). Therefore, Hence,

If we let , then . Also, the above becomes.

Thus,

Thus by the property of the MEX function that was proved,

This concludes the inductive step, and hence the theoerem is true for all finite games.