Problem 366

Stone Game III

Two players, Anton and Bernhard, are playing the following game.
There is one pile of $n$ stones.

The first player may remove any positive number of stones, but not the whole pile.
Thereafter, each player may remove at most twice the number of stones his opponent took on the previous move.
The player who removes the last stone wins.

E.g. $n=5$

If the first player takes anything more than one stone the next player will be able to take all remaining stones.
If the first player takes one stone, leaving four, his opponent will take also one stone, leaving three stones.
The first player cannot take all three because he may take at most $2\times 1=2$ stones. So let’s say he takes also one stone, leaving $2$. The second player can take the two remaining stones and wins.

So $5$ is a losing position for the first player.

For some winning positions there is more than one possible move for the first player.
E.g. when $n=17$ the first player can remove one or four stones.

Let $M(n)$ be the maximum number of stones the first player can take from a winning position at his first turn and $M(n)=0$ for any other position.

$\sum M(n)$ for $n\le 100$ is $728$.

Find $\sum M(n)$ for $n\le 10^{18}$. Give your answer modulo $10^8$.

取石子游戏（三）

两名玩家安东和伯恩哈德正在玩下面这个游戏。
有一堆共$n$枚石子。

先手玩家可以从堆中取走任意正数枚石子，但不能全部拿走。
此后，每名玩家可以从堆中取走的石子数目最多是其对手上一轮取走石子数目的两倍。
取走最后一枚石子的玩家获胜。

例如，若$n=5$

如果先手玩家取走多于一枚石子，后手玩家总能取走剩下的全部石子。如果先手玩家取走一枚石子，他的对手将同样取走一枚石子，留下三枚石子。
先手玩家不能取走全部三枚石子，因为他最多只能取走$2 \times 1 = 2$枚石子。若他又取走一枚石子，留下两枚。后手玩家可以取走剩下两枚石子并获胜。

因此$5$是先手玩家的必败态。

在某些必胜态时，先手玩家可能有不止一种可行操作。
例如，若$n=17$，先手玩家可以先取走一枚或四枚石子。

对于先手玩家的必胜态，记$M(n)$为先手玩家第一轮最多取走的石子数目；对于必败态，记$M(n)=0$。

对于所有$n\le 100$，$\sum M(n)$为$728$。

对于所有$n\le 10^{18}$，求$\sum M(n)$，并将其对$10^8$取余作为你的答案。

译注：“取石子游戏（二）”参见第325题。