Nimber

In mathematics, the nimbers, also called Grundy numbers, are introduced in combinatorial game theory, where they are defined as the values of nim heaps. They arise in a much larger class of games because of the Sprague–Grundy theorem which states that every impartial game is equivalent to a nim heap of a certain size. The nimbers are the ordinal numbers endowed with a new nimber addition and nimber multiplication, which are distinct from ordinal addition and ordinal multiplication. The minimum excludant operation is applied to sets of nimbers.

Nimber addition (also known as nim-addition) can be used to calculate the size of a single nim heap equivalent to a collection of nim heaps. It is defined recursively by

where the minimum excludant mex(S) of a set S of ordinals is defined to be the smallest ordinal that is not an element of S.

For finite ordinals, the nim-sum is easily evaluated on a computer by taking the bitwise exclusive or (XOR, denoted by ⊕) of the corresponding numbers. For example, the nim-sum of 7 and 14 can be found by writing 7 as 111 and 14 as 1110; the ones place adds to 1; the twos place adds to 2, which we replace with 0; the fours place adds to 2, which we replace with 0; the eights place adds to 1. So the nim-sum is written in binary as 1001, or in decimal as 9.

This property of addition follows from the fact that both mex and XOR yield a winning strategy for Nim and there can be only one such strategy; or it can be shown directly by induction: Let α and β be two finite ordinals, and assume that the nim-sum of all pairs with one of them reduced is already defined. The only number whose XOR with α is α ⊕ β is β, and vice versa; thus α ⊕ β is excluded. On the other hand, for any ordinal γ < α ⊕ β, XORing ξ ≔ α ⊕ β ⊕ γ with all of α, β and γ must lead to a reduction for one of them (since the leading 1 in ξ must be present in at least one of the three); since ξ ⊕ γ = α ⊕ β > γ, we must have α > ξ ⊕ α = β ⊕ γ or β > ξ ⊕ β = α ⊕ γ; thus γ is included as (β ⊕ γ) ⊕ β or as α ⊕ (α ⊕ γ), and hence α ⊕ β is the minimum excluded ordinal.

...
Wikipedia