Sylver Coinage（シルバー・コイネージ、John Conway のゲーム）をブラウザに実装した。2 人が交互に正の整数を言う。ただしすでに言われた数の和（同じ数を何度使ってもよい）で作れる数は言えない。1 を言った人の負け。硬貨の額面を順に決めていき、「もう作れる金額の硬貨は発行できない」と考えるとわかりやすい。言われた数の最大公約数が 1 になった時点で、言える数は有限個に減る。デモではその局面を厳密に解き、言える数ごとに勝ち手 ✓／負け手 ✗ を出す。最大公約数が 1 より大きいうちは言える数が無限にあり、探索ではなく理論しか頼れない。その理論には穴がある：素数 5 で始めれば先手必勝と証明されている（Hutchings の定理）のに、その勝ち方は証明からは出てこない。初手 16 が勝ちか負けかは今も未解決で、Conway が 1,000 ドルの懸賞をかけた。ソルバーは、局面を「言った数のどれか m を法とする各剰余類の最小元」（Apéry 集合）の m − 1 個の整数で表すメモ化 minimax。理論を信じずに、(1) Sicherman が公開している {m, n} の勝ち手の表を 175 行計算し直して全行一致、(2) Sicherman の論文（2002）の例をすべて再現、(3) 論文の「{12, 17} から到達できる局面は 158,793 個」が、こちらでは 158,792 個になる 1 個の差を突き止め、(4)「最大の数 t が勝ち手になる {m, n} は 7 組しか知られていない」を 528 組で調べ直して同じ 7 組だけを得た。テスト 14 件。ソルバー内蔵パズル第 101 弾。
デモ: https://sen.ltd/portfolio/sylver-coinage/
リポジトリ: https://github.com/sen-ltd/sylver-coinage
ルール
- 2 人が交互に正の整数を 1 つ言う。
- すでに言われた数の非負整数係数の和で表せる数は言えない。たとえば 5 と 4 が言われたあとは 4, 5, 8, 9, 10, 12, 13, … は言えない（12 = 4 + 4 + 4、13 = 4 + 4 + 5）。
- 1 を言った人の負け。1 は他のどの数からも作れないので最後まで言えるが、1 しか残っていなければそれを言うしかない。
Wikipedia の対局例：A が 5、B が 4、A が 11、B が 6、A が 7、B が 2、A が 3。残りは 1 だけで、B が負ける。デモの study モードで同じ手順を打つと、A の手がすべて相手を負け局面（P 局面）に送っていることが確かめられる（テストにも入れた）。
デモには 3 つのモードがある。コンピュータが先手（5, 7, 11 のどれかで始める）、自分が先手、両方自分で指す study。数をクリックすると言える。マウスを載せると、その数を言ったら言えなくなる数が薄くなる。
なぜ必ず終わるか、いつ有限になるか
言われた数の最大公約数を g とする。g の倍数でない数はいくら言われても作れないので、g > 1 の間は言える数が無限にある。ただし g の倍数のうち言えるものは有限個しかなく、それを言い尽くせば g が下がる。g は正の整数なので、ゲームは必ず終わる。
g = 1 になると、言える数は有限個になる。言われた数で作れる数の集合は数値半群で、言える数はそのギャップ、最大のギャップは Frobenius 数 t。2 つの互いに素な数 a, b なら Sylvester の公式 t = (a − 1)(b − 1) − 1 がある（ゲームの名前は Sylvester から）。{5, 14} なら t = 4 × 13 − 1 = 51、言える数は 26 個。
局面の持ち方：Apéry 集合
局面は「言える数の集合」だが、t が数百になると集合のままでは重い。そこで、すでに言われた数を 1 つ選んで m とし、
w[i] ＝ 作れる数のうち、m で割った余りが i の最小のもの（i = 0, 1, …, m − 1）
を持つ（数値半群論の Apéry 集合）。w[0] = 0 で、
- x が言える ⇔ x < w[x mod m]
- t ＝ max(w) − m
- 言える数の個数 ＝ Σ (w[i] − i) / m
{5, 14} なら w = [0, 56, 42, 28, 14] で、t = 56 − 5 = 51。
このゲームでは作れる数の集合は増える一方なので、最初に選んだ m は最後まで作れる数のまま残る。だからゲーム木全体を同じ m で表せて、局面は m − 1 個の小さな整数になる。{13, 21}（t = 239、言える数 120 個）でも 12 個の整数だ。
数 g を言うと、w[i] は「w[i − k·g] + k·g の最小（k ≥ 0）」に更新される。剰余 i → i + g (mod m) は gcd(g, m) 個の巡回に分かれるので、各巡回を 2 周して緩和すれば済む（3 周目は lcm(g, m) の倍数を足すだけで良くならない）。1 手 O(m)。
export function addInPlace(w: Int32Array, m: number, g: number): void {
const r = g % m;
if (r === 0) return;
const d = gcd(r, m);
for (let s = 0; s < d; s++) {
let i = s;
for (let step = 0; step < 2 * (m / d); step++) {
const j = i + r >= m ? i + r - m : i + r;
if (w[i] < INF && w[i] + g < w[j]) w[j] = w[i] + g;
i = j;
}
}
}
ソルバーは素直なメモ化 minimax で、1 以外の言える数を全部試す（1 は言った瞬間に負け）。1 しか残っていない局面は P。メモは m ごとに 1 つで、{m, n} を n について順に解くと前の結果がそのまま効く。検算として、局面を「言える数の集合」のまま持ち、手を「y − k·x が作れる数になる y を消す」で計算する素朴な別実装を書き、8 つの小さな初期局面から到達できる 3,754 局面すべてで勝敗が一致することを確かめた。
エンダー：勝てると分かるのに勝ち方が分からない
t は他の数を消さない（t より大きい数はもともと言えないし、t より小さい数を t の和で作ることはできない）。逆に t 以外の言える数がどれも t を消す局面を Sicherman は **ender（エンダー）**と呼んだ。
エンダーで t > 1 なら、手番の人が必ず勝つ。戦略盗用：
- t 以外に勝ち手があれば、それを指す。
- なければ t を指す。相手はそこから何かを言うが、それは t 以外の手で、どれも t を消す。つまり相手が言った数 u のあとの局面は、最初から自分が u を言った局面と同じ。仮定より u は負け手なので、相手は負け局面を自分に渡したことになる。
どちらの場合か分からないまま「勝てる」ことだけが分かる。
Hutchings の定理：互いに素な 2 数 {m, n} は必ずエンダー。だから 5 以上の素数 p で始めると、相手が何を返しても（返せるのは p と互いに素な数だけ）エンダーが自分の手番で来る。{2, 3} だけは t = 1 で例外だが、p ≥ 5 なら起きない。こうして {p} は P 局面、つまり素数 p ≥ 5 は勝つ初手と証明される。ただし実際にどの数で勝つかは、相手の返しごとに解かないと分からない。
デモで先手 5 を指し、相手が 14 を返すと {5, 14} になる。ここで勝ち手は 18 だけで、t = 51 は負け手だ。上の議論の後半（t を指す）は「t 以外に勝ち手がない」場合の話で、実際は t 以外に勝ち手があることがほとんどになる。
| {m, n} | 勝ち手（このソルバー） | Sicherman の表 |
|---|---|---|
| {4, 5} | 11 | [11] |
| {5, 6} | 19 | [19] |
| {7, 9} | 19, 24 | [19,24] |
| {10, 11} | 24, 28, 47 | [24,28,47] |
| {5, 14} | 18 | — |
| {5, 18} | 14, 16, 17 | 論文 §5 |
静かなエンダーと t の偶奇
Sicherman の論文（Theory and Practice of Sylver Coinage, Integers 2, 2002）は、t より小さい言える数 n がどれも「n を 1 回だけ使って」t を消すエンダーを quiet（静かな）エンダーと呼び、次を示した。
- 静かなエンダー ⇔ 0 < n < t のすべての n で「n と t − n のちょうど一方だけが言える」（反対称性）
- エンダーが静か ⇔ t が奇数（Odds and Enders 定理）
- どんな局面 S でも、「t/2 < n < t で n と t − n が両方言える n」を全部足した E(S) はエンダーになり、t は変わらない
{9, 11} と {10, 13} から到達できる 8,740 局面すべてで、エンダーの判定・反対称性・t の偶奇・E(S) がこれらの主張と一致することをテストで確かめた（うちエンダーは 349 局面、t > 1 のエンダーはすべて N 局面）。Roberts の等差数列の公式（a₀, a₀+d, …, a₀+sd の Frobenius 数）と、それがどの種類のエンダーかの分類（s = 1 は静か、a₀ = 3 & s = 2 は静かでない、a₀ > 3 は s | a₀ − 2 のときだけ静か）も、a₀ ≤ 15 の範囲で全部一致した。
Sicherman の表を計算し直す
Sicherman のサイトには {m, n}（4 ≤ m < n ≤ 40）の勝ち手の表がある（最終更新 2020-09-24）。互いに素な行は有限局面なので、このソルバーで全部計算できる。m ごとに 1 プロセスでメモを共有し、1,400 万局面を上限にして n の小さい順に解いた。
答えが載っている互いに素な行 207 行のうち 175 行を計算し、175 行すべてで勝ち手の集合が一致した。不一致は 0 行。m ≤ 8 は表の全行、いちばん大きい局面は {11, 30}（t = 289、言える数 145 個）。
| m | 計算した行 / 表の行 | n の範囲 | 最大の t | いちばん重い行 |
|---|---|---|---|---|
| 4 | 18 / 18 | ≤ 39 | 113 | {4,35} 0.0 秒 |
| 5 | 28 / 28 | ≤ 39 | 151 | {5,38} 0.0 秒 |
| 6 | 11 / 11 | ≤ 37 | 179 | {6,37} 0.2 秒 |
| 7 | 29 / 29 | ≤ 40 | 233 | {7,39} 1.4 秒 |
| 8 | 16 / 16 | ≤ 39 | 265 | {8,37} 7.5 秒 |
| 9 | 19 / 21 | ≤ 37 | 287 | {9,37} 33.0 秒 |
| 10 | 9 / 12 | ≤ 31 | 269 | {10,31} 46.8 秒 |
| 11 | 18 / 27 | ≤ 30 | 289 | {11,29} 97.3 秒 |
| 12 | 5 / 8 | ≤ 25 | 263 | {12,25} 85.0 秒 |
| 13 | 12 / 14 | ≤ 25 | 287 | {13,24} 164.2 秒 |
| 14 | 4 / 5 | ≤ 23 | 285 | {14,23} 378.5 秒 |
| 15 | 3 / 6 | ≤ 19 | 251 | {15,19} 99.3 秒 |
| 16 | 2 / 4 | ≤ 19 | 269 | {16,19} 210.9 秒 |
| 17 | 1 / 6 | ≤ 18 | 271 | {17,18} 603.4 秒 |
| 18 | 0 / 1 | — | — | — |
| 19 | 0 / 1 | — | — | — |
（Node 26、m ごとに 1 スレッド、3〜6 プロセス並列で計測した時間。）m が大きい行は局面数が急に増え、{13, 27}、{14, 25}、{15, 22}、{16, 21}、{17, 19}、{18, 19}、{19, 20} の 7 行が 1,400 万局面の上限で止まった。残り 25 行は、上限で止まった行より n が大きいので試していない。Sicherman が途中までしか書いていない 4 行（{13, 29} [56, … など）にも届かなかった。m を 1 増やすと Apéry 集合の次元が 1 増え、同じくらいの t でも到達局面の数が急に増える（{17, 18} は t = 271 で新しい局面 628 万）。
論文の本文に出てくる例も全部同じ結果になった。
- 単独勝ちの構成：{5, 14} [18]、{5, 18} [14, 16, 17]、{5, 14, 16, 18} [17]、{5, 16, 17, 18} [14]
- 勝ち手 [4, 5, 6, 7] の構成：{4, 9} [19]、{5, 9, 19} [31]、{6, 9, 19, 31} [17, 20, 22]、{7, 9, 19, 20, 31} [15]、そして {17, 18, 27, 33, 43} の勝ち手がちょうど 4, 5, 6, 7、56 を足すと 4, 5, 6, 7, 9（デモのスクリーンショットがこの局面）
- {4, 5, 7} は静かでないエンダー（t = 6）、{7, 8, 10, 13} は静かなエンダー（t = 19）、E({7, 11, 13, 15}) = {7, 11, 13, 15, 17, 19}
158,793 と 158,792
論文には「{12, 17} から到達できる局面は、{12, 17} 自身を含めて 158,793 個」とある。全部たどって数えると、こちらは 158,792 個だった。
1 個の差は「1 を言ったあとの局面」だ。こちらは 1 を手として展開しない（言った瞬間に負けなので局面として扱わない）。1 を言うと作れる数は全部の正の整数になり、どの局面からも同じ 1 つの局面に行く。これを数えると 158,793 になる。数え方の違いで、どちらも正しい。
t が勝ち手になる {m, n}
論文の脚注：
t が勝ち手になる {m, n} として知られているのは {2, 5}、{4, 5}、{5, 6}、{5, 9}、{8, 15}、{13, 14}、{13, 21} だけ。ほかにもあるか？（全部フィボナッチ数が絡むのか？）
{m, n, t} が P 局面かどうかを解けば分かる。t = 1 の {2, 3} は除く（1 を言うのは負けなので）。
m = 2〜17 について、m < n ≤ N の互いに素な n をすき間なく全部調べた（N は m = 2, 3 で 200、4 で 160、5 で 100、6 で 82、7, 8 で 40、9 で 37、10 で 32、11 で 30、12 で 28、13 で 26、14 で 24、15 で 21、16 で 20、17 で 18）。計 528 組のうち、t が勝ち手になるのは脚注の 7 組だけだった。新しい組は見つからず、7 組はすべて再現した。
5, 8, 13, 21 はフィボナッチ数で、9 と 14 と 15 は違う。「全部フィボナッチ数が絡む」は 7 組のどれにも m か n のどちらかにフィボナッチ数がある、という意味なら今のところ成り立っているが、理由は分からない。
無限局面：理論で分かること、分からないこと
g > 1 の局面は言える数が無限にあり、全探索はできない。デモでは次の順に調べる。
- {p}（p は 5 以上の素数）なら P（Hutchings）。g が 5 以上の素数なら g を言えば {g} になるので N。
- Sicherman のサイトの P 局面一覧（g = 2, 3, 4 の 264 局面と 1 系列）に載っていれば P。たとえば {4, 6}、{6, 9}、{8, 12}。
- 言える数 x を 120 まで試し、x のあとが「厳密に解いて P になる有限局面」か「既知の P 局面」になれば、x が勝ち手。
3 には枝刈りが効く。x のあとが有限でエンダー（t > 1）なら、上の戦略盗用でその局面は N なので、解かずに飛ばせる。1 つの数 n に互いに素な x を返すと、Hutchings の定理で必ずエンダーになるので、{n} に対する互いに素な返しは全部、探索なしで捨てられる。
初手を並べるとこうなる。
| 初手 | 結果 | 理由 |
|---|---|---|
| 1 | 負け | 1 を言った人の負け |
| 2, 3 | 負け | 相手が 3, 2 を返すと {2, 3}、残りは 1 だけ |
| 4 | 負け | 6 を返されると {4, 6} = P |
| 6 | 負け | 4 を返されると {4, 6}、9 を返されると {6, 9} |
| 8 | 負け | 12 を返されると {8, 12} = P |
| 9 | 負け | 6 を返されると {6, 9} = P |
| 12 | 負け | 8 を返されると {8, 12} = P |
| 素数 p ≥ 5 | 勝ち | Hutchings（勝ち方は構成されない） |
| p ≥ 5 の倍数 | 負け | p を返されると {p} = P |
| 16, 18, 24, 27, … | 未解決 | 2ᵃ3ᵇ の形。16 は Conway の $1000 問題 |
{4, 6} が P であることは、2 と 3 が互いに負け手（2 → 3、3 → 2 で {2, 3}）で、奇数の手 x はどれも {4, 6, x} が有限の N 局面になることから分かる。理論（Quiet End 定理）は「十分大きい奇数はすべて静かなエンダーになる」と保証し、このソルバーで x = 5, 7, …, 61 の 29 通りが全部 N になることをテストで確かめた。
初手 16 をデモで指すと、コンピュータは「勝ち手の候補を探索範囲内で見つけられない」と表示する。互いに素な返しは全部エンダーで捨てられ、偶数の返しは g = 2 の無限局面で、既知の P 局面にならない。ここから先が未解決問題だ。
実装メモ
-
src/sylver.ts：Apéry 集合、手の適用（巡回 2 周の緩和）、言える数・t・種数、極小生成系、エンダーの判定（quiet / unquiet）、E(S)、メモ化 minimax（Solver）、到達局面の数え上げ、Sylvester と Roberts の公式。 -
src/theory.ts：無限局面。既知の P 局面（data/sicherman-ppos.json）、Hutchings の定理、勝ち手の探索（エンダーの枝刈り付き）、初手の表。 -
tools/compute.mts：表の計算（table <m>）と t の判定（twins <m> <nMax>）。結果はruns/*.jsonl、tools/report.mtsがruns/summary.jsonとデモ下部の文章（src/findings.json）を作る。
まとめ
- Sylver Coinage は、言われた数の最大公約数が 1 になると有限ゲーム（数値半群のギャップを取り合う）になり、Apéry 集合で局面を m − 1 個の整数に詰めれば素直な minimax で解ける。
- エンダーでは戦略盗用で「勝てる」ことだけが分かり、Hutchings の定理により素数 p ≥ 5 は勝つ初手になる。勝ち方は相手の返しごとに解くしかない。
- Sicherman の表 175 行、論文の例すべて、t が勝つ 7 組を計算し直して、食い違いは「1 を言ったあとの局面を数えるか」の 1 個だけだった。
- 初手 16 は、互いに素な返しがすべてエンダーで消え、偶数の返しの先が無限局面のまま残る。そこが未解決問題の入り口になっている。