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$.

  • $\begingroup$ It seems familiar. I think that there may be a challenge related to this game or a similar one on projecteuler.net $\endgroup$ May 23, 2022 at 21:27
  • $\begingroup$ Only problem 433 (Step's in Euclid's algorithm) was mentioned by Professor Google. It is however only vaguely related. $\endgroup$ May 24, 2022 at 3:38
  • 1
    $\begingroup$ Found it: Project Euler problem 325: Stone Game II. The win condition is the variation of your last paragraph. $\endgroup$ May 24, 2022 at 8:01
  • $\begingroup$ @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. $\endgroup$ May 24, 2022 at 8:08
  • $\begingroup$ 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. $\endgroup$ Jun 29, 2022 at 16:11

1 Answer 1


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.

  • $\begingroup$ Great! Thank you very much. $\endgroup$ May 1 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.