World
Game
Of
Sprouts
Association

Genus Sequences

April 26, 2008

GRUNDY NUMBERS

The normal-play Grundy number of a game G, written Grundy+(G) is the unique nonnegative integer x such that o+(G+*x) = P. (Again, the superscripted plus signs here designate functions; the nonsuperscripted plus sign here indicates the concatenation of game components.)

Examples:

1. Grundy+(*0) = 0
2. Grundy+(*1) = 1
3. Grundy+(*1+*1) = 0
4. Grundy+(S1) = 0
5. Grundy+(S2) = 0
6. Grundy+(S2+*1) = 1

Similarly, the misere-play Grundy number of a game G, written Grundy-(G) is the unique nonnegative integer x such that o-(G+*x) = P.

Examples:

1. Grundy-(*0) = 1
2. Grundy-(*1) = 0
3. Grundy-(*1+*1) = 1
4. Grundy-(S1) = 1
5. Grundy-(S2) = 0
6. Grundy-(S2+*1) = 1

POP QUIZ

Fill in the blanks in the following:

1. Grundy+(*2+*2) = ?
2. Grundy-(*2+*2) = ?
3. Grundy+(*2+*3) = ?
4. Grundy-(*2+*3) = ?

GENUS SEQUENCES

The Genus of a game G, written Genus(G) is the unique infinite sequence of nonnegative integers a,b,c,d,e,... written abcde... such that

1. a = Grundy+(G)
2. b = Grundy-(G)
3. c = Grundy-(G+*2)
4. d = Grundy-(G+*2+*2)
5. e = Grundy-(G+*2+*2+*2)
6. etc.

Examples:

1. Genus(*0) = 01202020...
2. Genus(*1) = 10313131...
3. Genus(0P0) = 01202020...
4. Genus(0L0) = 10313131…
5. Genus(S2) = 00202020...

NIM-VALUES

The first two elements of Genus(G) = ab are referred to in Winning Ways, by Berlekamp, Conway and Guy, as the "nim-values" of G. For example, the nim-values of S2 are 00.