Problem 366: Stone Game III

Project Euler Problem 366 Solution

EulerSolve provides an optimized solution for Project Euler Problem 366, Stone Game III, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let $M(n)$ denote the largest winning first move in the Stone Game III position with $n$ stones, and define $$S(N)=\sum_{n=1}^{N} M(n).$$ The Project Euler task asks for $S(10^{18}) \bmod 10^8$. A direct scan of all positions up to $10^{18}$ is impossible, so the local solution replaces per-position game search by a recurrence on Fibonacci intervals. Mathematical Approach 1. Winning-Move Criterion Used by the Verifier The C++ file contains a slow checker based on Zeckendorf representations. For a positive integer $m$, let $z(m)$ be the smallest Fibonacci term appearing in its Zeckendorf decomposition. The checker tests every move $x$ with $1 \le x \lt n$ and uses the characterization $$2x \lt z(n-x).$$ Therefore the game-theoretic quantity implemented in all three language versions is $$M(n)=\max\left\{x \in \{1,\dots,n-1\}: 2x \lt z(n-x)\right\}.$$ The optimized solver never evaluates this inequality for every $n$. Instead, it exploits the block pattern that this rule creates when $n$ is grouped by Fibonacci ranges. 2. Fibonacci Interval Decomposition Use the same Fibonacci indexing as the code: $$F_0=1,\qquad F_1=1,\qquad F_{k+1}=F_k+F_{k-1}.$$ For each $k$, define the interval $$I_k=[F_k,\,F_{k+1}-1].$$ Its length is $$|I_k|=F_{k+1}-F_k=F_{k-1}.$$ Now let $A_k$ be the sequence of values $M(n)$ on $I_k$....

Detailed mathematical approach

Problem Summary

Two players face a single pile of $n$ stones. The first player removes any positive number of stones but not the whole pile; after that each player may remove at most twice as many as the opponent has just removed; whoever takes the last stone wins. Both play as well as they can. Let $M(n)$ be the largest number of stones the first player may take on his first turn and still win, and let $M(n)=0$ when $n$ is not a winning pile for him. We must find $\sum_{n\le 10^{18}}M(n)$ modulo $10^8$. ^[1] The statement gives three checks: $n=5$ is lost for the first player, so $M(5)=0$; from $n=17$ he wins by removing one or four stones, so $M(17)=4$; and $\sum_{n\le 100}M(n)=728$.

The whole solution in one sentence: a player loses exactly when the cap on his move is smaller than the smallest Fibonacci number needed to build the pile in front of him, and that one rule makes the largest winning opening move repeat a simple pattern between consecutive Fibonacci numbers, so the sum over $10^{18}$ piles becomes one closed-form piece per Fibonacci interval, $86$ of them in all.

Mathematical Approach

1. The game as a state, and the first values by hand

After the opening move only two numbers matter: how many stones are left and how many the mover may take. Write the state as $(m,b)$: $m$ stones remain and the mover may remove between $1$ and $\min(m,b)$ of them. Removing $x$ stones leads to the state $(m-x,2x)$, and $m=0$ means the previous player has just taken the last stone and won. A pile of $n$ stones puts the first player in the state $(n,n-1)$, because he may not take the whole pile. The game is finite with no draws, so under the normal play convention every state is won or lost for the mover. ^[7]

Small piles can be settled by hand. For $n=1$ the opening state is $(1,0)$: the first player has no legal move and loses. For $n=4$, taking one stone leaves $(3,2)$: the opponent may take one, leaving $(2,2)$ — we take both — or two, leaving $(1,4)$ — we take the last one. So $(3,2)$ is lost for him and $M(4)\ge 1$; taking two or three stones instead lets him clear the table at once, so $M(4)=1$. The same reasoning gives $M(n)$ for $n=1$ to $24$ as 0, 0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 1, 0, 1, 2, 3, 4, 5, 6, 2, 0, 1, 2, 3.

Two things stand out. The zeros sit at 1, 2, 3, 5, 8, 13, 21 — the Fibonacci numbers. And between two zeros the values climb by one and then break off into a shorter tail, which Section 7 shows to be a copy of part of an earlier interval and may contain several drops of its own. Both are proved below.

2. Fibonacci numbers and Zeckendorf's representation

Index the Fibonacci numbers the way the solution code does:

$$f_0=f_1=1,\qquad f_{k+1}=f_k+f_{k-1},$$

so that $f_1,f_2,f_3,\dots$ runs $1,2,3,5,8,13,21,\dots$: dropping the duplicate $f_0$ lists each Fibonacci number once. ^[5] Zeckendorf's theorem says that every positive integer $m$ is a sum of distinct Fibonacci numbers, no two of them neighbouring, in exactly one way, and that the greedy choice of the largest Fibonacci number not exceeding the rest produces it: ^[3]

$$m=f_{k_1}+f_{k_2}+\cdots+f_{k_r},\qquad k_i-k_{i+1}\ge 2 .$$

Write $z(m)=f_{k_r}$ for the smallest term of that representation. For instance $17=13+3+1$ gives $z(17)=1$, $20=13+5+2$ gives $z(20)=2$, and $100=89+8+3$ gives $z(100)=3$. A Fibonacci number is its own representation, so $z(f_k)=f_k$.

3. A lemma about Zeckendorf tails

Everything that follows rests on one inequality.

Lemma. For every $j\ge 1$ and every $d$ with $1\le d\lt f_j$,

$$z(d)+2d\le 2f_j .$$

The proof is induction on $j$. For $j=1$ there is no such $d$; for $j=2$ only $d=1$, and $1+2\le 4$. Let $j\ge 3$ and split the range of $d$ in three.

If $d\lt f_{j-1}$, the induction hypothesis already gives $z(d)+2d\le 2f_{j-1}\le 2f_j$.
If $d=f_{j-1}$, then $z(d)=d$ and the claim reads $3f_{j-1}\le 2f_{j-1}+2f_{j-2}$, that is $f_{j-3}\le f_{j-2}$, which is true.
If $f_{j-1}\lt d\lt f_j$, write $d=f_{j-1}+e$ with $1\le e\lt f_{j-2}$. Every Zeckendorf term of $e$ is at most $f_{j-3}$, so putting $f_{j-1}$ in front of them keeps the terms non-neighbouring, which means $z(d)=z(e)$. The hypothesis for $e$ gives $z(e)+2e\le 2f_{j-2}$, hence $z(d)+2d\le 2f_{j-2}+2f_{j-1}=2f_j$.

The bound cannot be improved. For odd $j\ge 3$ the number $f_j-1$ equals $f_{j-1}+f_{j-3}+\cdots+f_2$, so its smallest term is $2$ and $z(d)+2d=2f_j$ at $d=f_j-1$; for example $f_7-1=20=13+5+2$ and $2+40=2f_7$. A check over every $d\lt f_{17}=2584$ confirms the bound and its sharpness.

4. When is a position lost?

Theorem. For $m\ge 1$ the state $(m,b)$ is lost for the player to move if and only if $b\lt z(m)$.

Induct on $m$. Suppose first that $b\ge z(m)$. The mover takes $z(m)$ stones, which is legal because $z(m)\le\min(m,b)$. If $z(m)=m$ he has just taken the last stone and won. Otherwise the pile $m-z(m)$ keeps exactly the terms of $m$ above $f_{k_r}$, so its smallest term is

$$f_{k_{r-1}}\ge f_{k_r+2}=f_{k_r+1}+f_{k_r}\gt 2f_{k_r},$$

and the opponent is left with a cap $2z(m)$ strictly below $z\bigl(m-z(m)\bigr)$, a lost state by induction.

Suppose now that $b\lt z(m)$. If $b=0$ the mover cannot move and has lost. Otherwise he takes some $x$ with $1\le x\le b$, and $m-x\gt 0$ because $x\lt z(m)\le m$. Split that remainder as

$$m-x=(m-f_{k_r})+(f_{k_r}-x).$$

The right part lies between $1$ and $f_{k_r}-1$, so all of its terms are at most $f_{k_r-1}$, while the left part has no term below $f_{k_r+2}$; side by side the two lists are therefore the representation of $m-x$, and $z(m-x)=z(f_{k_r}-x)$. The Lemma with $j=k_r$ and $d=f_{k_r}-x$ gives $z(d)\le 2f_{k_r}-2d=2x$. Every move thus hands the opponent a cap $2x\ge z(m-x)$, a won state by induction, so $(m,b)$ is lost.

5. Lost piles and the winning first moves

The opening state is $(n,n-1)$, so a first move of $x$ stones wins exactly when $(n-x,2x)$ is lost, that is when

$$2x\lt z(n-x),\qquad 1\le x\le n-1 .$$

$M(n)$ is the largest such $x$, and $0$ if none exists. If $n$ is not a Fibonacci number, then $z(n)\lt n$, the move $x=z(n)$ is legal, and the first half of the proof above shows it wins. If $n=f_k$, then every legal $x$ is below $z(n)=n$ and the second half shows it loses. The lost piles are exactly the Fibonacci numbers, the pattern of the zeros in Section 1. ^[2] ^[4]

6. A two-case recursion for $M(n)$

Maximising $x$ is the same as minimising the pile $y=n-x$ that is left behind. Put $h(y)=z(y)+2y$; the winning condition $2(n-y)\lt z(y)$ becomes $h(y)\gt 2n$, so

$$M(n)=n-y^{*},\qquad y^{*}=\min\{\,y\ge 1: h(y)\gt 2n\,\},$$

as long as $y^{*}\le n-1$. Let $f_k$ be the largest Fibonacci number with $f_k\le n$. The Lemma says $h(y)\le 2f_k\le 2n$ for every $y\lt f_k$, so $y^{*}\ge f_k$, while $h(f_k)=3f_k$. Two cases follow.

If $2(n-f_k)\lt f_k$, then $h(f_k)\gt 2n$, so $y^{*}=f_k$ and $M(n)=n-f_k$. For $n=f_k$ this returns $0$, as it must.
Otherwise set $m=n-f_k$. Then $m$ lies between $\lceil f_k/2\rceil$ and $f_{k-1}-1$, a window with no Fibonacci number in it: $f_k\gt 2f_{k-2}$ puts $f_{k-2}$ below its left end, and $f_{k-1}$ is past its right end. By Section 5, $m$ is then a winning pile, so $1\le y^{*}(m)\le m-1\lt f_{k-1}$. For $1\le e\lt f_{k-1}$ the splitting argument of Section 4 gives $z(f_k+e)=z(e)$ and hence $h(f_k+e)=h(e)+2f_k$, so the condition $h(f_k+e)\gt 2n$ is simply $h(e)\gt 2m$; the identity therefore covers $y^{*}(m)$ and every smaller candidate. Since $h(f_k)\le 2n$ here, $y^{*}=f_k+y^{*}(m)$ and $M(n)=m-y^{*}(m)=M(m)$.

With $f_k$ the largest Fibonacci number not exceeding $n$, this is the whole of $M$:

$$M(n)=\begin{cases} n-f_k, & 2(n-f_k)\lt f_k,\\ M(n-f_k), & 2(n-f_k)\ge f_k. \end{cases}$$

For $n=17$ we get $f_6=13$ and $2\cdot 4\lt 13$, so $M(17)=4$, matching the statement. For $n=20$, $2\cdot 7\ge 13$ sends us to $M(7)$, where $2\cdot 2\lt 5$ gives $2$: the only winning opening from $20$ is to take two stones. For $n=100$, $2\cdot 11\lt 89$ gives $M(100)=11$. In the language of Section 2: strip Zeckendorf terms from the top while twice the remaining tail is at least the stripped term; $M(n)$ is the first tail smaller than half of its leading term. For $54=34+13+5+2$ the tails are $20$, then $7$, then $2$, and since $2\cdot 2\lt 5$ we stop with $M(54)=2$.

7. The sawtooth on one Fibonacci interval

Group the piles into the intervals $I_k=[f_k,f_{k+1}-1]$ for $k\ge 1$, whose length is $f_{k+1}-f_k=f_{k-1}$. Inside $I_k$ write $n=f_k+j$. The first case of Section 6 applies exactly while $2j\lt f_k$, that is for $j\lt P_k$ with

$$P_k=\lceil f_k/2\rceil ,$$

and there $M(n)=j$: the values climb $0,1,2,\dots,P_k-1$. The intervals $I_1,\dots,I_4$ end with that climb and have no tail. For $k\ge 5$ the positions from $j=P_k$ on remain, and there the second case replaces $n$ by $m=j$, which lands in $I_{k-2}$ at position $j-f_{k-2}$. Halving $f_k=2f_{k-2}+f_{k-3}$ gives

$$P_k=f_{k-2}+P_{k-3},$$

so that position starts at $P_{k-3}$, inside the climb of $I_{k-2}$, and runs to $P_{k-2}-1$, where that climb ends. The tail of $I_k$ is therefore the run $P_{k-3},\dots,P_{k-2}-1$ followed by the tail of $I_{k-2}$ itself. Written out, climb and tail separated:

$I_5=[8,12]$: $0,1,2,3\mid 1$;
$I_6=[13,20]$: $0,\dots,6\mid 2$;
$I_7=[21,33]$: $0,\dots,10\mid 3,1$;
$I_8=[34,54]$: $0,\dots,16\mid 4,5,6,2$;
$I_9=[55,88]$: $0,\dots,27\mid 7,8,9,10,3,1$.

The climb lengths $P_1,\dots,P_{12}$ are 1, 1, 2, 3, 4, 7, 11, 17, 28, 45, 72, 117, the halved Fibonacci numbers. ^[6] A count confirms the structure: the tail of $I_k$ has $f_{k-1}-P_k$ entries, and the description gives the same number,

$$\begin{aligned} &(P_{k-2}-P_{k-3})+(f_{k-3}-P_{k-2})\\ &\quad =f_{k-3}-P_{k-3}=f_{k-1}-P_k .\end{aligned}$$

8. The sum over one whole interval

Let $T_k$ be the sum of the tail of $I_k$ and let $U_k$ be the sum of $M$ over all of $I_k$. The climb contributes a triangular number, so

$$U_k=\frac{P_k(P_k-1)}{2}+T_k ,$$

where $T_1=T_2=T_3=T_4=0$. The tail description gives $T_5=1$, $T_6=2$ and, for $k\ge 7$,

$$T_k=T_{k-2}+\sum_{i=P_{k-3}}^{P_{k-2}-1} i .$$

That inner sum is a run of consecutive integers, so it closes in one multiplication, and both recursions reach only smaller indices. The first values are $U_1,\dots,U_9=$ 0, 0, 1, 3, 7, 23, 59, 153, 416 and $T_5,\dots,T_{12}=$ 1, 2, 4, 17, 38, 98, 280, 710. Running totals $C_k=U_1+\cdots+U_k$ finish the preparation.

9. The sum over part of an interval

For a limit $N$, let $f_K\le N\lt f_{K+1}$ and $j=N-f_K$. Then

$$\sum_{n\le N}M(n)=C_{K-1}+V_K(j),$$

where $V_K(j)$ sums the first $j+1$ values of $I_K$. For $j\lt P_K$ it is $j(j+1)/2$. Otherwise add the whole climb, $P_K(P_K-1)/2$, and set $t=j-P_K$, the offset inside the tail. For $K\ge 7$ the first tail block runs from $P_{K-3}$ to $P_{K-2}-1$, of length $B=P_{K-2}-P_{K-3}$: if $t\lt B$, add the integers $P_{K-3}$ to $P_{K-3}+t$ and stop, otherwise add the whole block and carry on in the tail of $I_{K-2}$ with offset $t-B$. The one-entry tails of $I_5$ and $I_6$ are worth $1$ and $2$, and every step lowers $K$ by $2$.

For $N=87$ the descent runs once. Here $87\in I_9=[55,88]$, $j=32$, $P_9=28$ and $t=4$. The climb gives $27\cdot 28/2=378$; the first tail block is $7,8,9,10$ of length $B=P_7-P_6=4$ and sum $34$; as $t=B$ we continue at offset $0$ in the tail of $I_7$, which is $3,1$, and add $3$. So $V_9(32)=378+34+3=415$, and with $C_8=246$ the total up to $87$ is $661$.

10. The checkpoint $\sum_{n\le 100}M(n)=728$

Here $f_{10}=89\le 100\lt 144=f_{11}$, so $K=10$ and $j=11$. The complete intervals $I_1,\dots,I_9$ contribute

$$C_9=0+0+1+3+7+23+59+153+416=662 .$$

Since $P_{10}=45$, the index $11$ is still inside the climb, so $V_{10}(11)=11\cdot 12/2=66$, and $662+66=728$, the value quoted in the statement. The same machinery gives $83085$, $9142038$, $792624636$ and $73233921484$ for $n\le 10^3,10^4,10^5,10^6$, each confirmed by adding up $M(n)$ one pile at a time.

11. The run up to $10^{18}$

$f_{86}=679891637638612258$ is the largest Fibonacci number not exceeding $10^{18}$, and $f_{87}=1100087778366101931$ is past it, so $K=86$ and

$$j=10^{18}-f_{86}=320108362361387742 .$$

Since $P_{86}=f_{86}/2=339945818819306129$ is larger than $j$, the limit sits inside the climb of its own interval, and the answer is $C_{85}$ plus $j(j+1)/2$. That total has $35$ decimal digits, so it needs more than $64$ bits. Every other value obeys the same bound: $M(n)\le n-1$ keeps the interval sums and running totals below $N^2$, and the products in $j(j+1)/2$ and in a run of consecutive integers below $4N^2\lt 2^{128}$, while $f_k$, $P_k$ and the offsets stay below $2N\lt 2^{63}$ — which is how the code picks its widths. Only at the end is the total reduced modulo $10^8$, a simple choice rather than a forced one: $2$ has no inverse modulo $10^8$, so the halving in $j(j+1)/2$ cannot be done by multiplication there, but halving whichever of $j$ and $j+1$ is even before reducing would serve as well.

How the Code Works

All three files build the same tables and answer a single query. In the C++ file ^[8] the struct Precomputed and the function build_precomputed fill fib with $f_0=f_1=1$, $f_2=2,\dots$ up to the first entry above the limit, so that kmax = fib.size() - 2 is the largest index whose Fibonacci number still fits. Four tables follow, in an order that has every value ready when it is needed: prefix_len holds $P_k$, seeded with 1, 1, 2, 3, 4 for $k=1,\dots,5$ and continued by fib[k-2] + prefix_len[k-3]; tail_sum holds $T_k$, seeded with $T_5=1$ and $T_6=2$ and continued by tail_sum[k-2] + sum_range(...), the recursions of Sections 7 and 8; interval_sum holds $U_k$ as tri(p-1) + tail_sum[k]; and interval_prefix_sum accumulates those into $C_k$. The helpers tri and sum_range are the closed forms for $0+1+\cdots+n$ and for a run of consecutive integers, so every table entry is constant work.

prefix_tail(data, k, j) is the walk of Section 9 through the tail blocks: while $j$ reaches past the current run it adds the whole run with sum_range and calls itself with $k-2$ and a reduced $j$, and it stops at the hand-coded tails of $I_5$ and $I_6$. prefix_interval(data, k, idx) returns tri(idx) inside the climb and tri(p-1) + prefix_tail(...) beyond it; its first line is a shortcut that returns the stored $U_k$ when idx is the last position of the interval, a value the recursive branch reproduces anyway (checked at every position of $I_1,\dots,I_{19}$). fast_sum_M scans fib upward for the interval holding $n$, adds interval_prefix_sum[k-1] to the partial interval, and main prints that sum modulo $10^8$.

The C++ file also carries a slow cross-check. smallest_zeckendorf_term computes $z(m)$ greedily from the top and drops two indices after each subtraction, which is precisely the non-neighbouring condition of Section 2. slow_sum_M tabulates $z$ up to its limit and then takes, for every $n$, the largest $x$ with 2*x < z[n-x] — the definition of $M(n)$ from Section 5 — at a cost of $O(L^2)$. run_checkpoints builds the tables for $10^6$, checks that the slow and the fast sum both give $728$ for $n\le 100$ and that they agree for $n\le 1000$, and main skips all of it when given --skip-checkpoints.

The Python and Java files mirror the C++ one function by function and leave out the cross-check. Arithmetic is the only real difference. C++ keeps the accumulated sums in unsigned __int128, the Fibonacci values, climb lengths and offsets in uint64_t and the table indices in std::size_t; Java uses BigInteger for the sums, long for the values and offsets and int for the indices; Python needs no decision at all. One pitfall: C++ writes its seed entries before the tables are known to be long enough, so build_precomputed must not be called with a limit below $8$ — a limit of $5$ to $7$ leaves room for prefix_len[5] but not for tail_sum[6], and below $5$ an earlier seed already runs off the end. The Python constructor raises IndexError for a limit below $3$, and the Java version guards each seed assignment with a size test. The published calls use $10^6$ and $10^{18}$, so they all have room.

Complexity and Verification

Exactly $86$ Fibonacci numbers do not exceed $10^{18}$; the table holds $88$ entries, $f_0$ to $f_{87}$, keeping the duplicate $1$ and the first value above the limit. With $K=86$ the four filling loops perform $81$, $80$, $84$ and $86$ constant-cost updates, so preparation needs $O(\log N)$ arithmetic operations on $O(\log N)$ stored integers of $O(\log N)$ bits. A query adds the upward scan for the interval, $O(\log N)$ again, and the tail walk, which drops two levels per step: at most $40$ descents from $k=86$, and none for this limit, which lands in a climb. The optional cross-check is the expensive part, $O(L^2)$ for $L=1000$: about $10^6$ comparisons. All three programs finish in well under a second and print the same value; the C++ one passes its checkpoints.

Every claim above was also checked independently of the solution files. A direct minimax over the game graph, with no Fibonacci theory in it, labels the $90000$ states $(m,b)$ with $1\le m,b\le 300$, and its labels agree with the criterion $b\lt z(m)$ in every case; the states with $b=0$ are lost too, as rules and criterion both demand. Four routes to $M(n)$ — that minimax, the maximum over $x$ of $2x\lt z(n-x)$, the two-case recursion of Section 6 and the Zeckendorf-tail rule — agree for every $n\le 400$, where the piles with $M(n)=0$ are exactly 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377. The sums $U_k$ and $T_k$ match brute-force sums over $I_1,\dots,I_{14}$, and the structural formula reproduces the running total $\sum_{n\le N}M(n)$ for every $N\le 3000$ and at $N=10^6$. A second summation, organised differently — a partial interval as a triangular number plus a difference of two values of the sum itself, instead of the tail tables — reproduces the published programs' output for $N=10^{18}$ exactly. One gap: the cross-check inside the C++ file uses the same Zeckendorf criterion as the fast path, so on its own it tests the tables, not the game analysis; the minimax closes that gap.

Footnotes and References

The sources below supply the background used above; the Lemma of Section 3, the recursion of Section 6 and the interval sums of Sections 7 to 9 are derived in full here.

Project Euler 366 — Stone Game III. The official statement describes one pile of n stones from which the first player may remove any positive number but not the whole pile, after which nobody may remove more than twice the opponent's last take; the last stone wins. It defines M(n) as the maximum winning first move and 0 otherwise, notes that 5 is a losing pile and that from 17 one or four stones win, gives 728 as the sum for n ≤ 100 and asks for the sum up to 10^18 modulo 10^8.
Wikipedia — Fibonacci nim. It states the same rules, says that the first player loses exactly when the starting pile is a Fibonacci number, and gives the winning move as the smallest term of the pile's Zeckendorf representation; more generally a player loses when the quota is smaller than that term — the criterion proved in Section 4. It also notes that other winning moves may exist, which is why M(n) asks for the largest.
Wikipedia — Zeckendorf's theorem. Every positive integer is a sum of distinct Fibonacci numbers, no two of them consecutive, in exactly one way, and the greedy choice of the largest Fibonacci number at each stage produces that representation; the example given is 64 = 55 + 8 + 1, while 34 + 21 + 8 + 1 is not one, since 34 and 21 are consecutive.
M. J. Whinihan, Fibonacci Nim, The Fibonacci Quarterly 1 (1963), no. 4, pp. 9–13. The first published analysis of this game, in the December 1963 issue, establishing the losing piles and the strategy that Sections 4 and 5 re-derive; the game itself is credited there to Robert E. Gaskell.
OEIS A000045 — Fibonacci numbers. The sequence F(n) = F(n−1) + F(n−2) with F(0) = 0 and F(1) = 1, listed as 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …; the f_k of Section 2 is F(k+1), so f_0 and f_1 are the two copies of 1.
OEIS A173173 — ceiling(Fibonacci(n)/2). The sequence 0, 1, 1, 1, 2, 3, 4, 7, 11, 17, … of halved Fibonacci numbers rounded up; the climb lengths of Section 7 are these numbers, P_k being the term at index k+1.
Wikipedia — Combinatorial game theory. The article describes the normal play convention, under which the player unable to move loses, and notes that any finite game with two possible results can be put into that form; this is the convention Section 1 uses to call every state won or lost.
C++ — Euler366.cpp. The linked immutable revision contains build_precomputed, prefix_tail, prefix_interval, fast_sum_M, slow_sum_M and run_checkpoints, together with the --skip-checkpoints flag. It is the implementation record for this article.

Problem 366 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;
using u128 = unsigned __int128;

constexpr u64 kLimit = 1000000000000000000ULL;
constexpr u64 kMod = 100000000ULL;

struct Precomputed {
    std::vector<u64> fib;        // fib[0]=1, fib[1]=1, fib[2]=2, ...
    std::vector<u64> prefix_len; // P_k
    std::vector<u128> tail_sum;  // tail sum in interval k
    std::vector<u128> interval_sum;
    std::vector<u128> interval_prefix_sum;
};

u128 tri(const u64 n) {
    return static_cast<u128>(n) * static_cast<u128>(n + 1ULL) / 2U;
}

u128 sum_range(const u64 a, const u64 b) {
    if (b < a) {
        return 0;
    }
    const u64 len = b - a + 1ULL;
    return static_cast<u128>(a + b) * static_cast<u128>(len) / 2U;
}

Precomputed build_precomputed(const u64 max_n) {
    Precomputed data;
    data.fib = {1ULL, 1ULL, 2ULL};  // index 0..2
    while (data.fib.back() <= max_n) {
        const std::size_t sz = data.fib.size();
        data.fib.push_back(data.fib[sz - 1] + data.fib[sz - 2]);
    }

    const std::size_t kmax = data.fib.size() - 2;  // largest interval index with fib[k] <= max_n

    data.prefix_len.assign(data.fib.size(), 0ULL);
    data.tail_sum.assign(data.fib.size(), 0U);
    data.interval_sum.assign(data.fib.size(), 0U);
    data.interval_prefix_sum.assign(data.fib.size(), 0U);

    // Base prefix lengths.
    data.prefix_len[1] = 1;
    data.prefix_len[2] = 1;
    data.prefix_len[3] = 2;
    data.prefix_len[4] = 3;
    data.prefix_len[5] = 4;

    for (std::size_t k = 6; k <= kmax; ++k) {
        data.prefix_len[k] = data.fib[k - 2] + data.prefix_len[k - 3];
    }

    // Tail sums for intervals.
    data.tail_sum[5] = 1;
    data.tail_sum[6] = 2;
    for (std::size_t k = 7; k <= kmax; ++k) {
        const u64 a = data.prefix_len[k - 3];
        const u64 b = data.prefix_len[k - 2] - 1ULL;
        data.tail_sum[k] = data.tail_sum[k - 2] + sum_range(a, b);
    }

    // Sum of M(n) over a full interval [F_k, F_{k+1}-1].
    data.interval_sum[1] = 0;
    data.interval_sum[2] = 0;
    for (std::size_t k = 3; k <= kmax; ++k) {
        const u64 p = data.prefix_len[k];
        data.interval_sum[k] = tri(p - 1ULL) + data.tail_sum[k];
    }

    for (std::size_t k = 1; k <= kmax; ++k) {
        data.interval_prefix_sum[k] = data.interval_prefix_sum[k - 1] + data.interval_sum[k];
    }

    return data;
}

u128 prefix_tail(const Precomputed& data, const std::size_t k, const u64 j) {
    if (j == static_cast<u64>(-1)) {
        return 0;
    }
    if (k <= 4) {
        return 0;
    }
    if (k == 5) {
        return 1;
    }
    if (k == 6) {
        return 2;
    }

    const u64 start = data.prefix_len[k - 3];
    const u64 end = data.prefix_len[k - 2] - 1ULL;
    const u64 block_len = end - start + 1ULL;

    if (j < block_len) {
        return sum_range(start, start + j);
    }
    return sum_range(start, end) + prefix_tail(data, k - 2, j - block_len);
}

u128 prefix_interval(const Precomputed& data, const std::size_t k, const u64 idx) {
    const u64 interval_len = data.fib[k - 1];
    if (idx >= interval_len - 1ULL) {
        return data.interval_sum[k];
    }
    if (k <= 2) {
        return 0;
    }

    const u64 p = data.prefix_len[k];
    if (idx < p) {
        return tri(idx);
    }

    const u64 tail_idx = idx - p;
    return tri(p - 1ULL) + prefix_tail(data, k, tail_idx);
}

u128 fast_sum_M(const u64 n, const Precomputed& data) {
    if (n == 0ULL) {
        return 0;
    }

    std::size_t k = 1;
    while (k + 1 < data.fib.size() && data.fib[k + 1] <= n) {
        ++k;
    }

    const u128 full_before = data.interval_prefix_sum[k - 1];
    const u64 idx = n - data.fib[k];
    return full_before + prefix_interval(data, k, idx);
}

u64 smallest_zeckendorf_term(u64 n, const std::vector<u64>& fib12) {
    std::size_t i = fib12.size() - 1;
    u64 smallest = 0;
    while (n > 0ULL) {
        while (fib12[i] > n) {
            --i;
        }
        n -= fib12[i];
        smallest = fib12[i];
        if (i >= 2) {
            i -= 2;
        } else {
            break;
        }
    }
    return smallest;
}

u64 slow_sum_M(const int limit) {
    std::vector<u64> fib12 = {1ULL, 2ULL};
    while (fib12.back() <= static_cast<u64>(limit)) {
        const std::size_t sz = fib12.size();
        fib12.push_back(fib12[sz - 1] + fib12[sz - 2]);
    }

    std::vector<u64> z(static_cast<std::size_t>(limit + 1), 0ULL);
    for (int i = 1; i <= limit; ++i) {
        z[static_cast<std::size_t>(i)] = smallest_zeckendorf_term(static_cast<u64>(i), fib12);
    }

    u64 total = 0;
    for (int n = 1; n <= limit; ++n) {
        u64 best = 0;
        for (int x = 1; x < n; ++x) {
            if (2ULL * static_cast<u64>(x) < z[static_cast<std::size_t>(n - x)]) {
                best = static_cast<u64>(x);
            }
        }
        total += best;
    }
    return total;
}

bool run_checkpoints() {
    const Precomputed data = build_precomputed(1000000ULL);

    const u64 slow_100 = slow_sum_M(100);
    if (slow_100 != 728ULL) {
        std::cerr << "Checkpoint failed: slow sum for n<=100\n";
        return false;
    }

    const u128 fast_100 = fast_sum_M(100ULL, data);
    if (fast_100 != 728ULL) {
        std::cerr << "Checkpoint failed: fast sum for n<=100\n";
        return false;
    }

    const u64 slow_1000 = slow_sum_M(1000);
    const u128 fast_1000 = fast_sum_M(1000ULL, data);
    if (fast_1000 != slow_1000) {
        std::cerr << "Checkpoint failed: slow/fast mismatch for n<=1000\n";
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    bool skip_checkpoints = false;
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            skip_checkpoints = true;
        } else {
            std::cerr << "Unknown argument: " << arg << '\n';
            return 1;
        }
    }

    if (!skip_checkpoints && !run_checkpoints()) {
        return 2;
    }

    const Precomputed data = build_precomputed(kLimit);
    const u128 total = fast_sum_M(kLimit, data);
    const u64 answer = static_cast<u64>(total % static_cast<u128>(kMod));
    std::cout << answer << '\n';
    return 0;
}

Python

def tri(n):
    return n * (n + 1) // 2

def sum_range(a, b):
    if b < a: return 0
    return (a + b) * (b - a + 1) // 2

class Precomputed:
    def __init__(self, max_n):
        self.fib = [1, 1, 2]
        while self.fib[-1] <= max_n:
            self.fib.append(self.fib[-1] + self.fib[-2])
            
        kmax = len(self.fib) - 2
        
        self.prefix_len = [0] * len(self.fib)
        self.tail_sum = [0] * len(self.fib)
        self.interval_sum = [0] * len(self.fib)
        self.interval_prefix_sum = [0] * len(self.fib)
        
        self.prefix_len[1] = 1
        self.prefix_len[2] = 1
        self.prefix_len[3] = 2
        self.prefix_len[4] = 3
        if len(self.prefix_len) > 5:
            self.prefix_len[5] = 4
            
        for k in range(6, kmax + 1):
            self.prefix_len[k] = self.fib[k - 2] + self.prefix_len[k - 3]
            
        if len(self.tail_sum) > 5: self.tail_sum[5] = 1
        if len(self.tail_sum) > 6: self.tail_sum[6] = 2
        for k in range(7, kmax + 1):
            a = self.prefix_len[k - 3]
            b = self.prefix_len[k - 2] - 1
            self.tail_sum[k] = self.tail_sum[k - 2] + sum_range(a, b)
            
        self.interval_sum[1] = 0
        self.interval_sum[2] = 0
        for k in range(3, kmax + 1):
            p = self.prefix_len[k]
            self.interval_sum[k] = tri(p - 1) + self.tail_sum[k]
            
        for k in range(1, kmax + 1):
            self.interval_prefix_sum[k] = self.interval_prefix_sum[k - 1] + self.interval_sum[k]

def prefix_tail(data, k, j):
    if j < 0: return 0
    if k <= 4: return 0
    if k == 5: return 1
    if k == 6: return 2
    
    start = data.prefix_len[k - 3]
    end = data.prefix_len[k - 2] - 1
    block_len = end - start + 1
    
    if j < block_len:
        return sum_range(start, start + j)
    return sum_range(start, end) + prefix_tail(data, k - 2, j - block_len)

def prefix_interval(data, k, idx):
    interval_len = data.fib[k - 1]
    if idx >= interval_len - 1:
        return data.interval_sum[k]
    if k <= 2: return 0
    
    p = data.prefix_len[k]
    if idx < p:
        return tri(idx)
        
    tail_idx = idx - p
    return tri(p - 1) + prefix_tail(data, k, tail_idx)

def fast_sum_M(n, data):
    if n == 0: return 0
    k = 1
    while k + 1 < len(data.fib) and data.fib[k + 1] <= n:
        k += 1
        
    full_before = data.interval_prefix_sum[k - 1]
    idx = n - data.fib[k]
    return full_before + prefix_interval(data, k, idx)

def solve():
    kLimit = 1000000000000000000
    kMod = 100000000
    data = Precomputed(kLimit)
    total = fast_sum_M(kLimit, data)
    ans = total % kMod
    return str(ans)

if __name__ == '__main__':
    print(solve())

Java

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class Euler366 {
    static final long kLimit = 1000000000000000000L;
    static final long kMod = 100000000L;

    static BigInteger tri(long n) {
        return BigInteger.valueOf(n).multiply(BigInteger.valueOf(n + 1)).divide(BigInteger.valueOf(2));
    }

    static BigInteger sumRange(long a, long b) {
        if (b < a)
            return BigInteger.ZERO;
        long len = b - a + 1;
        return BigInteger.valueOf(a + b).multiply(BigInteger.valueOf(len)).divide(BigInteger.valueOf(2));
    }

    static class Precomputed {
        List<Long> fib;
        long[] prefixLen;
        BigInteger[] tailSum;
        BigInteger[] intervalSum;
        BigInteger[] intervalPrefixSum;

        Precomputed(long maxN) {
            fib = new ArrayList<>();
            fib.add(1L);
            fib.add(1L);
            fib.add(2L);
            while (fib.get(fib.size() - 1) <= maxN) {
                int sz = fib.size();
                fib.add(fib.get(sz - 1) + fib.get(sz - 2));
            }

            int kmax = fib.size() - 2;
            int size = fib.size();

            prefixLen = new long[size];
            tailSum = new BigInteger[size];
            intervalSum = new BigInteger[size];
            intervalPrefixSum = new BigInteger[size];

            for (int i = 0; i < size; i++) {
                tailSum[i] = BigInteger.ZERO;
                intervalSum[i] = BigInteger.ZERO;
                intervalPrefixSum[i] = BigInteger.ZERO;
            }

            prefixLen[1] = 1;
            if (size > 2)
                prefixLen[2] = 1;
            if (size > 3)
                prefixLen[3] = 2;
            if (size > 4)
                prefixLen[4] = 3;
            if (size > 5)
                prefixLen[5] = 4;

            for (int k = 6; k <= kmax; k++) {
                prefixLen[k] = fib.get(k - 2) + prefixLen[k - 3];
            }

            if (size > 5)
                tailSum[5] = BigInteger.valueOf(1);
            if (size > 6)
                tailSum[6] = BigInteger.valueOf(2);

            for (int k = 7; k <= kmax; k++) {
                long a = prefixLen[k - 3];
                long b = prefixLen[k - 2] - 1;
                tailSum[k] = tailSum[k - 2].add(sumRange(a, b));
            }

            intervalSum[1] = BigInteger.ZERO;
            if (size > 2)
                intervalSum[2] = BigInteger.ZERO;

            for (int k = 3; k <= kmax; k++) {
                long p = prefixLen[k];
                intervalSum[k] = tri(p - 1).add(tailSum[k]);
            }

            for (int k = 1; k <= kmax; k++) {
                intervalPrefixSum[k] = intervalPrefixSum[k - 1].add(intervalSum[k]);
            }
        }
    }

    static BigInteger prefixTail(Precomputed data, int k, long j) {
        if (j < 0)
            return BigInteger.ZERO;
        if (k <= 4)
            return BigInteger.ZERO;
        if (k == 5)
            return BigInteger.ONE;
        if (k == 6)
            return BigInteger.valueOf(2);

        long start = data.prefixLen[k - 3];
        long end = data.prefixLen[k - 2] - 1;
        long blockLen = end - start + 1;

        if (j < blockLen) {
            return sumRange(start, start + j);
        }
        return sumRange(start, end).add(prefixTail(data, k - 2, j - blockLen));
    }

    static BigInteger prefixInterval(Precomputed data, int k, long idx) {
        long intervalLen = data.fib.get(k - 1);
        if (idx >= intervalLen - 1) {
            return data.intervalSum[k];
        }
        if (k <= 2)
            return BigInteger.ZERO;

        long p = data.prefixLen[k];
        if (idx < p) {
            return tri(idx);
        }

        long tailIdx = idx - p;
        return tri(p - 1).add(prefixTail(data, k, tailIdx));
    }

    static BigInteger fastSumM(long n, Precomputed data) {
        if (n == 0)
            return BigInteger.ZERO;

        int k = 1;
        while (k + 1 < data.fib.size() && data.fib.get(k + 1) <= n) {
            k++;
        }

        BigInteger fullBefore = data.intervalPrefixSum[k - 1];
        long idx = n - data.fib.get(k);
        return fullBefore.add(prefixInterval(data, k, idx));
    }

    static String solve() {
        Precomputed data = new Precomputed(kLimit);
        BigInteger total = fastSumM(kLimit, data);
        long ans = total.remainder(BigInteger.valueOf(kMod)).longValue();
        return Long.toString(ans);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}