# Euclid's algorithm as a combinatorial game

Consider the following two player game based on the Euclidean algorithm: Positions are given by $$(a,b)$$ in $$\mathbb N^2\setminus\{(0,0)\}$$ (where $$\mathbb N=\{0,1,2,\ldots\}$$) defining a greatest common divisor in $$\mathbb N$$. Moves are given by $$(a,b)\longrightarrow (\min(a,b),\max(a,b)-k\min(a,b))$$ for $$k$$ in $$\{1,\ldots,\lfloor \max(a,b)/\min(a,b)\rfloor\}$$ where we assume $$\min(a,b)>0$$. Two players move in turn until arriving at $$(d,0)$$ or $$(0,d)$$. At this point, the player who can no longer move announces the greatest common divisor $$d$$ of $$a$$ and $$b$$ defining the initial position $$(a,b)$$ and wins.

Winning positions are easy to describe: $$(a,b)$$ is winning if and only if $$\min(a,b)/\max(a,b)$$ is smaller than the inverse $$(-1+\sqrt{5})/2$$ of the golden number $$(1+\sqrt{5})/2$$.

Has this game be described somewhere?

The variation where the last player with a move (i.e. playing a position $$(a,b)$$ with $$\min(a,b)$$ a divisor of $$\max(a,b)$$) wins is also easy to describe: A position $$(a,b)$$ is winning if either $$(a=b)$$ or if $$ab>0$$ and $$\max(a,b)/\min(a,b)>(1+\sqrt{5})/2$$.

• It seems familiar. I think that there may be a challenge related to this game or a similar one on projecteuler.net May 23, 2022 at 21:27
• Only problem 433 (Step's in Euclid's algorithm) was mentioned by Professor Google. It is however only vaguely related. May 24, 2022 at 3:38
• Found it: Project Euler problem 325: Stone Game II. The win condition is the variation of your last paragraph. May 24, 2022 at 8:01
• @PeterTaylor : Indeed, I searched with the keyword 'Euclid' which turned up nothing (By the way, the name "Stone Game II" really does not say a lot on the nature of the game). Thanks. May 24, 2022 at 8:08
• The variation is described in A. J. Cole and A. J. T. Davie, A Game Based on the Euclidean Algorithm and a Winning Strategy for It, The Mathematical Gazette vol. 53, no. 386 (1969), pp354-357. Jun 29, 2022 at 16:11

Following up on Peter Taylor's answer, here's a fairly complete annotated bibliography.

What you describe as the variant came first:
A. J. Cole and A. J. T. Davie, A game based on the Euclidean algorithm and a winning strategy for it, Math. Gaz. 53 (1969) 354-357. https://doi.org/10.2307/3612461

The analysis of your initial game was posed and answered in Mathematics Magazine:
J. W. Grossman, A Nim-type game, Problem #1537, Math. Mag. 70 (1997) 382. https://doi.org/10.1080/0025570X.1997.11996580
P. D. Straffin, Solution to Problem #1537, Math. Mag. 71 (1998) 394-395. https://doi.org/10.1080/0025570X.1998.11996686

Using continued fractions in the analysis:
T. Lengyel, A Nim-type game and continued fractions, Fibonacci Quart. 41 (2003) 310-320. https://www.fq.math.ca/Scanned/41-4/lengyel.pdf

Refining the N-positions of your initial game*:
G. Nivasch, The Sprague-Grundy function of the game Euclid, Discrete Math. 306 (2006) 2798-2800. https://doi.org/10.1016/j.disc.2006.04.020

Using the structure of the Calkin-Wilf tree in the analysis:
S. Hofmann, G. Shuster, J. Steuding, Euclid, Calkin & Wilf--playing with rationals, Elem. Math. 63 (2008) 109-117. https://doi.org/10.4171/EM/95

Refining the N-positions of your variant game*:
G. Cairns, N. B. Bao, T. Lengyel, The Sprague-Grundy function of the real game Euclid, Discrete Math. 311 (2011) 457-462. https://doi.org/10.1016/j.disc.2010.12.011

*The N- and P-position analysis of the two versions of the game is the same, but refining the N-positions by their Sprague-Grundy values differs.

• Great! Thank you very much. May 1 at 15:03