Each move divides the group into the sum of two groups. The general rule for computing Nimbers is that the assigned Nimber is the smallest value that cannot be reached at the next stage. We also know that there are no moves possible for 1 and 2 dots so that G(1) = G(2) = 0.
For example, there is a single legal move from a group of three and that move leads to two games whose Nimber is 0. Therefore the smallest number we cannot reach is 1 hence G(3) = 1.
Starting from a row of four, there is only one legal division since (2, 2) is forbidden by the rules. This leaves (1, 3) (or the equivalent (3, 1). We know that G(1) = 0 and G(3) = 1 and therefore the only Nimber we can achieve starting with a row of four is one. The smallest number we cannot get is zero which is therefore the value of this position G(4) = 0.
From 5 we can reach (1, 4) which has value 0 + 0 = 0 and we can reach (2, 3) which has value 0 + 1 = 1. Therefore the smallest number we cannot achieve is 2 and G(5) = 2.
def compute_grundy_table:
nimber = (n + 1) * [0]