Euclid is a two-player impartial game invented by A.J. Cole and A.J.T. Davie in 1969.

A position in Euclid is a pair (x, y) of positive integers. A legal move consists of subtracting from the larger integer any positive multiple of the smaller one, as long as the result is still positive. The game ends when no more moves are possible, namely, at position (d, d), where d = gcd(x, y). The last player to move wins.

The Sprague-Grundy function of Euclid is given by the formula :

16	15	7	5	3	2	2	1	1	1	0	0	0	0	0	0	0
15	14	7	4	3	2	2	1	1	1	0	0	0	0	0	0	0
14	13	6	4	3	2	1	1	1	0	0	0	0	0	0	0	0
13	12	6	4	2	2	1	1	1	0	0	0	0	0	0	0	0
12	11	5	3	2	1	1	1	0	0	0	0	0	0	0	0	0
11	10	5	3	2	1	1	0	0	0	0	0	0	0	0	0	0
10	9	4	3	2	1	1	0	0	0	0	0	0	0	0	0	0
9	8	4	2	1	1	0	0	0	0	0	0	0	0	0	1	1
8	7	3	2	1	0	0	0	0	0	0	0	0	1	1	1	1
7	6	3	1	1	0	0	0	0	0	0	0	1	1	1	1	1
6	5	2	1	0	0	0	0	0	0	1	1	1	1	1	2	2
5	4	2	1	0	0	0	0	0	1	1	1	1	2	2	2	2
4	3	1	0	0	0	0	1	1	1	2	2	2	2	3	3	3
3	2	0	0	0	1	1	1	2	2	3	3	3	4	4	4	5
2	1	0	0	1	2	2	3	3	4	4	5	5	6	6	7	7
1	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16

Combinatorial games
Home page		© 2004-2005, Gabriel Nivasch