Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Is every finite octal game eventually periodic?

Open
OctalGames.guy_question

by martelus trismortuus · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatorial-game-theoryimpartial-gamesoctal-gamesopen-problem

Let Γ=d0.d1d2⋯dk\Gamma = d_0.d_1d_2\cdots d_kΓ=d0​.d1​d2​⋯dk​ be any octal game of finite length, and let GΓ(n)\mathcal G_\Gamma(n)GΓ​(n) be the nim-value of a Γ\GammaΓ-heap of nnn tokens (see the definition OctalGames_Code). Then the nim-sequence of Γ\GammaΓ is eventually periodic: there exist n0≥0n_0\ge 0n0​≥0 and p≥1p\ge 1p≥1 such that

GΓ(n+p)=GΓ(n)for all n≥n0.\mathcal G_\Gamma(n+p)=\mathcal G_\Gamma(n)\qquad\text{for all } n\ge n_0 .GΓ​(n+p)=GΓ​(n)for all n≥n0​.

This is the question "Is every finite octal game eventually periodic?" asked in Winning Ways and recorded by Siegel as unresolved. Many octal games are known to be periodic: by the Octal Periodicity Theorem, a finite computation suffices once periodicity has set in (Kayles has period 12 and preperiod 71; the game 0.1060.1060.106 has a period exceeding 3×10113\times10^{11}3×1011). For others, such as 0.0070.0070.007 and 0.60.60.6, no period has been found despite extensive computation. A disproof would exhibit a finite octal code whose nim-sequence is not eventually periodic.

Formalization Note Codes are arbitrary finite digit lists, including those with a nonzero d0d_0d0​ (splitting without removing tokens); see the definition's note for the treatment of d0d_0d0​. No bound on n0n_0n0​ or ppp is required.

Preamble
import Mathlib
import Definitions.Def_OctalGames_Code
open OctalGames
Formal statement
theorem OctalGames.guy_question (c : Code) : EventuallyPeriodic c := by sorry
Source
A. N. Siegel, Combinatorial Game Theory, GSM 146, AMS 2013, Section IV.2, p. 194: 'Question. Is every finite octal game eventually periodic?' (a question from Winning Ways, Berlekamp-Conway-Guy, 1982; also listed in Siegel's Appendix A). Definitions pp. 188-191.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me