New Results in Sylver Coinage

G. L. Sicherman AT&T 480 Red Hill Road Middletown, N.J. 07748 gls@hrcms.ATT.COM

December 7, 1991

Of Silver we have heard no more. —Stevenson, Treasure Island

1 Introduction

The Coin Problem in number theory is the problem of finding the largest sum that cannot be paid with coins of given denominations. The problem was studied by Frobenius and by Sylvester [1]. Sylvester showed that for two coins of denominations m and n, where m and n are coprime, the largest unpayable sum is (m − 1)(n − 1) − 1. Sylver Coinage is J. H. Conway’s game of denominating coins. Two players take turns choosing a number. A number may not be chosen if it can be expressed as a sum (with repetitions) of numbers chosen previously; such a number is said to be eliminated. The player who chooses 1 loses.

2 First Principles

Following Grundy and Smith [3], let a position be an N -position if the player next to play can win; that is, if its Sprague-Grundy number is nonzero. Otherwise let it be a P-position (for “previous”). The greatest common divisor of the moves in a position S is denoted by g(S), or g for short. The greatest legal move in S is denoted by t(S), or t for short; this is defined only if g(S) = 1. If S = {x_{1}, ..., x_{n}}, then S × k = {kx_{1}, ..., kx_{n}}. Similarly, if S = {kx_{1}, ..., kx_{n}}, then S ÷ k = {x_{1}, ..., x_{n}}. Regardless of the value of g(S), we write t̄(S) = g(S)t(S ÷ g(S)). For example, t̄({6, 8}) = 10, because t({3, 4}) = 5.

A position S in Sylver Coinage is determined by a set of previous moves {x_{1}, ..., x_{n}}. Different sets of moves can create the same position; e.g., {10} = {10, 20, 30}. Every position has a unique minimal representation, obtained by discarding every move that is eliminated by the moves that are smaller than it. This canonical representation is used here tacitly.

If T can be obtained from S by making moves in S, then T is said to be later than S, written S < T. This relation defines a partial order on positions.

After the first move, at most finitely many legal moves do not lower the value of g. Since g can be lowered only finitely many times, the game must end after finitely many moves. In other words, there is no infinite sequence of positions S_{0} < S_{1} < S_{2} < .... This prevents games from going on forever. But a game’s remaining duration is unlimited while g > 1, because the players can play an arbitrarily long descending volley of moves not divisible by g. For example, in {4, 6} the next moves may be 9999, 9997, 9995 ... .

The initial move 2 loses to 3, because in {2, 3} all moves are eliminated except 1. Likewise the initial move 3 loses to 2. In general, if x is answered by y, then y is answered by x unless y eliminates x; two moves that answer each other are said to be paired. In {} 4 and 6 are paired, because in {4, 6} only odd moves are legal, and the odd moves are paired (5, 7), (9, 11), .... It is only slightly harder to show that {6, 9} is P.

It is known that {8, 12} is P, but the proof requires a two-tiered pairing, one for the even moves and one for the odd.

3 Hutchings’s Theorem

The most important general result in Sylver Coinage is due to R. L. Hutchings:

If m and n are coprime and greater than 3, then {m, n} is N.

A position is an end-position, or ender, if any move other than t eliminates t. Otherwise the position is a non-ender. Let Sn denote the position formed by adding n to position S. Hutchings’s proof has two parts. The first part shows that all enders are N. This is easy: if t wins in an ender S, the next player can play it and win; if t loses to some other move u, then Stu is P; since S is an ender, Stu = Su, and u wins in S. The second part of the proof, omitted here, shows that {m, n} is an ender.

An immediate corollary is that any prime p greater than 3 wins in {}! The only replies not coprime with p are its multiples, which are illegal moves. Thus the second player’s move must create an N -position.

4 Quiet Enders

An ender S is said to be a quiet ender if t is eliminated by every legal move u using just one instance of u. For example, S = {4, 5, 7} is an ender, since t = 6 is eliminated by 1, 2, 3, and 6; but it is not a quiet ender, because to express 6 as a sum of numbers from {3, 4, 5, 7} you must use 3 twice.

The Quiet End Theorem says that if n is coprime with u and with v, then (S × u)n is a quiet ender if and only if (S × v)n is. We will see later how to use the Quiet End Theorem in analyzing positions.

5 The Pattern Theorem

Positions with g = 1 are finite and can be analyzed exhaustively. Positions with g > 1 are infinite, and in general do not yield to analysis. However, when g = 2 there is a bound on the size of a winning move, so any position with g = 2 can be analyzed exhaustively [2]. The proof relies on induction for even moves, and for odd moves on the fact that the analysis can be computed by a finite-state automaton. Such an automaton must cycle eventually.

For larger values of g the calculation is multidimensional and cannot be modeled with a finite-state automaton.

6 Analyzing Positions

Positions with g = 1 can be analyzed by exhaustion—in fact, they must be; even if a position is known to be an ender, its winning moves must be found by exhaustion. Fortunately, enders that arise in the analysis need not be solved. Unfortunately, few positions are enders, and the labor of calculation grows exponentially with the size of the numbers in the position. The position {31, 37} is known to have a winning move, but nobody has come near to calculating it.

Positions with g > 1 are more challenging. Here the Quiet End Theorem becomes useful. For example, {2, 3, n} is trivially a quiet ender for any n > 1. By the theorem, {4, 6, n} is also a quiet ender, and this establishes that {4, 6} is P. Similarly {6, 9} is P. The result does not hold for {8, 12} because of the requirement that n be coprime with 4, but the theorem does tell us that {8, 12}n is N for odd n. Nor does the result hold for {10, 15}, because {5} is P.

In positions for which g is divisible by a prime p greater than 3, Hutchings’s Theorem guarantees that p is a winning move. But the position may have other winning moves as well: in {15, 20, 25} 9 and 11 win as well as 5.

The Quiet End Theorem can make a finite analysis suffice even when g > 1. For example, {12, 15, 18} is P. How do we know? To begin with, t̄ = 21, so the only moves that leave g = 3 are 3, 6, 9, and 21. We know that 3 is answered by 2, and 6 and 9 answer each other, and 21 is answered by 4. For large enough moves not divisible by 3, we can apply the Quiet End Theorem. Since {4, 5, 6, n} is a quiet ender for legal n ≥ 8, therefore {12, 15, 18, n} is a quiet ender for legal n ≥ 8. We call a position with prime g short if sufficiently large moves in it produce quiet enders, and long if sufficiently large moves in it produce non-enders. Because {12, 15, 18} is short, the only moves not divisible by 3 that we must examine are those ≤ 7.

Short positions are often P. Long ones hardly ever are. By the Pattern Theorem, the replies for a position with g = 2 will eventually fall into a pattern, but “eventually” can be very late indeed! The position {8, 10} is modest enough; it is short and easily shown to have no odd winning moves. But the inevitable pattern in the replies arises only after hundreds of odd moves.

In fact, the pattern is generally so long in coming that a winning odd move is almost sure to occur first, unless the position is short. The only long positions known to be P are {8, 10, 22} and the members of the series {8, 12, 8n+2, 8n+6} for n ≥ 1. For these positions the Pattern Theorem is justified; for all others it is almost useless. Given a long position, we can be nearly certain that it has a winning move, though it may take years to discover one.

7 First-Order Analysis of {8}

F. Voelkle has found all the winning moves in {8} and analyzed some of the ensuing positions with g = 2. This position offers a good illustration of practical analysis. In what follows, the set of winning moves in a position is expressed as a sequence in brackets; for example, {6} [4, 9] means that 4 and 9 are winning moves in the position {6}.

Hutchings’s Theorem tells us that odd moves in {8} cannot win. That leaves the even moves. To begin with, 2 is answered by 3, and 4 by 6. The long {8, 10, 22} is P; it has a simple pairing strategy for odd moves greater than 5. That {8, 12} is P has already been discussed.

Besides 12, the only other winning move in {8} is 14. How do we know? Inasmuch as {8, 14} is short, only a few odd moves must be examined. The even moves must be judged case by case: 10 and 12 are paired, 18 is answered by 25, 20 is answered by 9, 26 is answered by 17, and 34 is answered by 27.

We can write off all even moves in {8} greater than t̄(8, 14) = 34, because they can be answered with 14. That leaves 18, 20, 22, 26, and 34. Of these, 20 is undercut by 12, and 22 by 14. The odd move 35 wins in {8, 34}, showing that short positions are sometimes vulnerable to moves not divisible by g. As for 18 and 26, analyzing deeper gives us the P-positions {8, 18, 28} and {8, 20, 26}.

Are there any other P-positions containing 8 with g = 2? Yes, infinitely many if you include the series {8, 12, 8n + 2, 8n + 6}. But there can be only finitely many others! Trying to generate a series of P-positions from positions with g = 4 works only for {8, 12} and {8, 20}, because other positions of the form {8, 8n + 4} have the winning move 14. And {8, 20} has the winning move 26, so for sufficiently large n, 26 wins in {8, 20, 4n + 2} and in {8, 20, 4n + 2, 4n + 6}.

In fact, the only other known P-positions containing 8 with g = 2 are the short positions {8, 20, 30} and {8, 34, 36}. Although {8, 34, 36} is short, to solve it you must solve its long offspring, such as {8, 34, 36, 46} [71], {8, 34, 36, 54}

\begin{matrix}\{6, 22, 38\} & [4, 469] & \{10, 34, 46\} & [353] \\ \{6, 34, 56\} & [4, 237] & \{10, 36, 42, 58\} & [217] \\ \{8, 26, 28, 38\} & [205] & \{12, 16, 20, 34, 42\} & [431] \\ \{8, 30, 34, 52\} & [393, 405] & \{12, 16, 20, 42, 50\} & [537] \\ \{8, 34, 36, 62\} & [647, 669] & \{12, 16, 20, 62, 66, 70\} & [215] \\ \{8, 34, 44, 46\} & [201, 203] & \{12, 26, 28, 70\} & [209] \\ \{8, 34, 44, 70\} & [36, 405] & \{14, 16, 22, 34\} & [265, 305] \\ \{10, 14, 26\} & [293] & \{14, 16, 24, 26, 34\} & [373] \\ \{10, 26, 28, 32\} & [217] & \{14, 18, 26, 38\} & [501] \\ \{10, 26, 94\} & [251] & \{14, 22, 26\} & [931] \\ \{10, 28, 32, 36, 54\} & [233, 245, 247] & \{14, 26, 32\} & [1513] \\ \{10, 34, 46, 58, 82\} & [275] & \{16, 22, 26, 28, 30, 34, 36\} & [649] \end{matrix}

Table 1: Solutions to some long positions.

[173], and {8, 34, 36, 62} [647, 669]. The status of {8, 30, 34} is unknown; it has no winning moves below 2000.

8 Known Results When g = 2

Solving long positions requires more stubbornness than cleverness. In {6, 22, 38} it is obvious that 4 wins, reducing the position to {4, 6}. As the position is long, it ought to have also an odd winning move, and so it does: 469. Strategically, 469 is the superior move, because it limits the rest of the game. But tactically it complicates the position enormously.

The only known wins in {10} are 5 and 14. The other possible wins are 26, 32, 36, and 46. Of these, 26 probably wins; the only unsolved moves in {10, 26} produce long positions. By the same token {10, 32, 48} is probably P: it is short, it has no odd winning moves, and all even moves lose or produce long positions.

The only known win in {12} is 8. Low moves of the form 4n+2 are answered thus: {10, 12} [7, 18]; {12, 14} [16]; {12, 18} [10, 15, 16, 21]; {12, 22} [16, 30]; {12, 26} [28, ...]; {12, 30} [22, ...]; {12, 34} [20, ...]; {12, 38} [20, ...]; {12, 42} [20, ...]. Thus the least possible winning move of the form 4n + 2 in {12} is 46.

The known wins in {14} are 7, 8, and 10. The only unsolved possible winning move is 26. Among the losers are {14, 16} [8, 12]; {14, 18} [5]; {14, 20} [10]; {14, 22} [9, ...]; {14, 24} [8, 10, ...]; {14, 38} [17, ...]; {14, 48} [8, 9, 10, ...].

Solutions to some of the longest positions appear in Table 1. These short positions are known to be P: {4, 6}, {8, 14}, {8, 18, 28}, {8, 20, 26}, {8, 20, 30}, {8, 34, 36}, {10, 12, 18}, {10, 14, 16, 18}, {10, 14, 18, 22}, {10, 14}, {10, 16, 24}, {10, 18, 26, 34}, {10, 26, 34, 42}, {10, 28, 32, 36}, {12, 14, 16, 18, 20}, {12, 14, 16}, {12, 14, 20, 22}, {12, 16, 18}, {12, 16, 20, 22, 26}, {12, 16, 22}, {12, 20, 22, 28, 30}, {12, 20, 26, 28, 34}, {12, 20, 28, 30, 38}, {12, 20, 28, 34, 42}, {12, 20, 28, 38, 46}, {12, 20, 28, 42, 50}, {12, 20, 34}, {12, 20, 38}, {12, 20, 42}, {12, 22, 26, 28, 32}, {12, 22, 26, 40}, {12, 22, 30, 32, 40}, {12, 22, 30}, {12, 26, 28, 42, 44}, {12, 26, 28}, {12, 26, 34, 44}, {12, 28, 30, 32, 34}, {14, 16, 18, 20, 22, 24}, {14, 16, 20, 26}, {14, 18, 22, 24, 26, 30}, {16, 18, 20, 22}, {16, 18, 22, 26}, {16, 20, 22, 24, 26, 28, 30}, {16, 20, 26, 28, 38}, {16, 20, 28, 30, 42}, {16, 20, 28, 38, 50}, {16, 22, 26, 28}, {16, 26, 28, 30}.

9 Known Results When g = 3

Positions with g = 3 require more labor than positions with g = 2. The short {6, 9}, {12, 15, 18}, and {12, 18, 21} are P. The long {12, 15, 21} is unsolved. Obviously 6 wins in the long {9, 15, 21}, but is there a winning move with g = 1?

The position {12, 27} is N, but no winning move is known for it! If 21 loses, then 42 wins.

10 Known Winning Moves in {m, n}

Table 2 is an extended and corrected version of Table 7 in Richard Nowakowski’s recent paper [4]. The indices at the left and the top are the first two moves; the table entries are the winning third moves, if any.

11 Synthetic Methods

Another way of studying Sylver Coinage is to take some numbers and look for a position in which those numbers are the winning moves. Formally, a move n wins in a position S if and only if Sn is P and Sn ≠ S. We begin by establishing the Separation Lemma:

If u and v are distinct winning moves in S, there exists T > S such that u wins in T and v does not.

The proof is constructive. We are given that Su and Sv are P. If Suv = Sv, then v is a winning move in Su, contrary to the hypothesis that Su is P. Thus Suv ≠ Sv. Since Sv is P, Suv must be N; let w be a winning move in Suv, so that Suvw is P. Since w is a legal move in the P-position Sv, Svw must be N, whence Suvw ≠ Svw. Let T = Svw. Clearly u is legal and wins in T, and v does not, being illegal.

The Separation Lemma can be used to prove the Single Win Theorem:

For any n ≥ 2 there exists a position in which n alone wins.

6  7  8  9  10
7 [16]
8  [4]  [5]
9  P  [19,24]  [21]
10  [4]  [12]  [22]  [16]
11 [26]  [24,34]  [23]  [13,30]  [24,28,47]
12 [4,9]  [10]  P  [6]  [7,18]
13 [23,28]  [4]  [25]  [11]  [28]
14  [4]  P  P  [22,48]  P
15  [9]  [16]  [97]  [6]  [5]
16 [4,7]  [6,15]  [12,14]  [10]  [9,24]
17 [38]  [50]  [23]  [22,59]  [59]
18 [4,9]  [38]  [28]  [6]  [12]
19  [5]  [9]  [39]  [4,7]  [44]
20  [4]  [92]  [12,26,30]  [61,95]  [5,14,26?,32?,36?,46?]
21  [9]  P  [9]  [6,8]  [128]
22  [4]  [61]  [10,14]  [14,17]  [8]
23 [13]  [55]  [11,17]  [74,139]  [48,54]
24 [4,9] [9,11,26]  [12,14]  [6,7]  [11,14,16]
25 [46]  [47,83]  [13]  [32]  [5]
26 [4,11] [24,58]  [20]  [128]  [44?,58?,68?]
27  [9]  [127]  [33,55]  [6]  [62]
28 [4,13]  P  [12,14,18]  [67,87]  [11,13,14]
29 [68]  [153]  [30]  [86,102]  [64,66]
30 [4,9]  [94]  [14,20,29,34?] [6,11]  [5,14,26?,32?,36?,46?]
31 [47]  [158]  [185]  [5]  [54,119]
32  [4]  [122]  [12,14]  [25,101] [48?,66?,78?,98?,108?,118?]
33  [9]  [149]  [27]  [6]  [128,217]
34  [4]  [11]  [30?,35,36]  [245]  [14]
35 [62]  P  [34]  [164]  [5]

Table 2a: Solutions to positions of the form {m, n}.

11  12  13  14  15
12  [49]
13 [9,19]  [59]
14  [93]  [16]  [155]
15 [102]  [18,21?]  [17,55] [62,66]
16 [57,58] [8,14,18,22] [137,140] [8,12]  [7]
17 [24,71]  [50,105]  [15,27] [38,74] [13,29]
18 [68,118] [10,15,16,21]  [164]  [5]  [12]
19  [13]  [61]  [11]  [59]  [
20 [46,63] [8,34,38,42] [35,56]  [10]  [5]
21 [94,167] [15?,18,27?]  [  [7]  [12?,
22  P  [16,30]  [  [9,  [
23  [8]  [135,146]  [6]  [  [
24 [7,10,17]  [8,  [  [8,10,  [
25 [81,123]  [  [8,  [27,  [5]
26  [6]  [28,  P  [  [
27  [79]  [  [17,  [25,  [
28 [10,46]  [8,26,  [  [7,8,10,  [

Table 2b: Solutions to positions of the form {m, n}.

We start by constructing a position in which n wins. Let p be a prime that is greater than 3 and does not divide n. By Hutchings’s Theorem {p, n} is N. Let w be a winning move in {p, n}. Then {p, n, w} is P. Also by Hutchings’s Theorem, {p, w} is N, so {p, w} ≠ {p, n, w}. Thus n is a legal and winning move in {p, w}.

Let S_{0} = {p, w}. If n alone wins in S_{0}, we are done. If not, use the Separation Lemma to find S_{1} such that S_{0} < S_{1} and n wins in S_{1}. If n alone wins in S_{1}, we are done; otherwise repeat the process. Since an infinite ascending chain does not exist, the algorithm must eventually terminate in a position in which n alone wins.

To illustrate, let n = 14. Using p = 5 gives us {5, 14} [18]. Solving S_{0} = {5, 18} gives [14, 16, 17]. Let us eliminate 16 by solving {5, 14, 16, 18}; the unique winning move is 17. Then S_{1} = {5, 16, 17, 18}, and this has the desired unique winning move 14.

Conjecture: any set of mutually indivisible numbers greater than 3 is the set of winning moves in some position.

No general construction for this conjecture is known. To show how to attempt it, let the numbers be [4, 5, 6, 7]. Choose a number bigger than all the numbers and coprime with them; 9 will do. Solving {4, 9} gives us 19, so 4 wins in {9, 19}. Does 5 win? No: {5, 9, 19} [31]. However, {4, 9, 19, 31} = {4, 9, 19}, so we can add 31 to the position. We now have {9, 19, 31} [4, 5, ...].

Does 6 win in {9, 19, 31}? No: {6, 9, 19, 31} [17, 20, 22]. But adding 20 to the position has no effect on 4 or 5. We now have {9, 19, 20, 31} [4, 5, 6, ...].

Does 7 win in {9, 19, 20, 31}? No: {7, 9, 19, 20, 31}15! Adding 15 to the position has no effect on 5 (15=5+5+5) or 6 (15=6+9), but 15 is not eliminated by 4.

This looks unpromising. Instead of adding 15 to {9, 19, 20, 31}, can we add two moves so as to let 7 win without affecting 4, 5, and 6? The moves that do not affect 4, 5, and 6 are 24, 25, 30, ... but we can stop now, because larger moves do not affect 7 either. Only 24 affects 7 without affecting 4, 5, or 6.

When we reach a dead end, the thing to do is recurse. At any stage of the search we can try to add several moves instead of one. As a last resort we can choose a new starting move; there are always more to choose from!

Probabilistically speaking, the search is certain to succeed, unless we can prove beforehand that it must fail. (But we must beware of unwanted winning moves!) As for [4, 5, 6, 7], one position that works is {17, 18, 27, 33, 43}. By good fortune, adding 56 to this position lets us add 9 to the set of winning moves: {17, 18, 27, 33, 43, 56} [4, 5, 6, 7, 9].

Another conjecture that arises naturally is:

Conjecture. For any n ≥ 3 there exists a position with g = 2 in which n wins.

You can create other conjectures by using other values of g.

12 Sprague-Grundy Theory

Little progress has been made in computing Sprague-Grundy numbers for Sylver Coinage positions. The value of G({4}) is not 6 as has been speculated [2]. Here are some values for odd moves:

\begin{matrix}n & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 & 23 & 25 & 27 & 29 \\ G(\{4, n\}) & 2 & 3 & 5 & 8 & 9 & 14 & 16 & 16 & 21 & 23 & 25 & 25 & 29 & 30 \end{matrix}

And here are some values for even moves. Those for high n are conjectural until a pattern is found.

\begin{matrix}n & 2 & 6 & 10 & 14 & 18 & 22 & 26 & 30 & 34 & 38 & 42 \\ G(\{4, n\}) & ω & 0 & 1 & 4 & 6 & 7 & 10 & 11 & 12 & 13 & 15 \end{matrix}

The values dovetail perfectly so far. Thus the value of G({4}) may well be ω +1.

13 Wanted — Dead or Alive

The following simple positions are O-positions, or outlaws that have eluded capture. Whoever shuts one or more of them behind brackets will earn the order of the Sylver Bullet and the thanks of a grateful citizenry.

{8, 30, 34}
{10, 26, 44}
{10, 32, 44, 48}
{10, 32, 48, 54}
{12, 15, 21}

And these N -positions deserve to be held for further questioning:

\begin{matrix}\{6, 32, 58\} & [4, … \\ \{6, 34, 62\} & [4, … \\ \{8, 26, 30\} & [12, … \\ \{9, 15, 21\} & [6, … \\ \{10, 18, 44\} & [12, … \end{matrix}

References

[1] J. J. Sylvester, Mathematical Questions from the Educational Times 41 (1884), p. 21 (q. 7382).

[2] E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Academic Press, 1982, pp. 575–606.

[3] P. M. Grundy and C. A. B. Smith, “Disjunctive Games with the Last Player Losing,” Proceedings of the Cambridge Philosophical Society 52 (1956), pp. 527–533.

[4] R. J. Nowakowski, “…, Welter’s Game, Sylver Coinage, Dots-and-Boxes, …,” in R. Guy (ed.), Combinatorial Games, Proceedings of Symposia on Applied Mathematics 43, Amer. Math. Soc., Providence, 1991.