---

Problem 882

---

Removing Bits

Dr. One and Dr. Zero are playing the following partisan game.
The game begins with one $1$, two $2$’s, three $3$’s, $\ldots$, $n$ $n$’s. Starting with Dr. One, they make moves in turn.

Dr. One chooses a number and changes it by removing a $1$ from its binary expansion.

Dr. Zero chooses a number and changes it by removing a $0$ from its binary expansion.

The player that is unable to move loses.
Note that leading zeros are not allowed in any binary expansion; in particular nobody can make a move on the number $0$.

They soon realize that Dr. Zero can never win the game. In order to make it more interesting, Dr. Zero is allowed to “skip the turn” several times, i.e. passing the turn back to Dr. One without making a move.

For example, when $n = 2$, Dr. Zero can win the game if allowed to skip $2$ turns. A sample game:
$$
[1, 2, 2]\xrightarrow{\textrm{Dr. One}}[1, 0, 2]\xrightarrow{\textrm{Dr. Zero}}[1, 0, 1]\xrightarrow{\textrm{Dr. One}}[1, 0, 0]\xrightarrow[\textrm{skip}]{\textrm{Dr. Zero}}
[1, 0, 0]\xrightarrow{\textrm{Dr. One}}[0, 0, 0]\xrightarrow[\textrm{skip}]{\textrm{Dr. Zero}}[0, 0, 0].
$$
Let $S(n)$ be the minimal number of skips needed so that Dr. Zero has a winning strategy.

For example, $S(2) = 2$, $S(5) = 17$, $S(10) = 64$.

Find $S(10^5)$.

---

移除比特

壹博士和零博士正在玩一个游戏。
游戏开始时有一个$1$、两个$2$、三个$3$、$\ldots$、和$n$个$n$。壹博士先行，然后双方交替行动。

轮到壹博士行动时，壹博士可以选择一个数，并从其二进制表示中移除一个$1$。

轮到零博士行动时，零博士可以选择一个数，并从其二进制表示中移除一个$0$。

首先无法行动的玩家输掉游戏。
注意二进制表示中不允许有前导零；特别地，双方在行动时均不能选择数$0$进行移除。

他们很快意识到零博士永远不可能获胜。为了让这个游戏更有趣，零博士可以有限次地“跳过回合”，即不进行任何行动并将局面直接转交给壹博士。

例如，当$n = 2$时，若零博士能跳过$2$个回合就能获胜。一种可能的获胜方式是:
$$
[1, 2, 2]\xrightarrow{\textrm{壹博士}}[1, 0, 2]\xrightarrow{\textrm{零博士}}[1, 0, 1]\xrightarrow{\textrm{壹博士}}[1, 0, 0]\xrightarrow[\textrm{跳过}]{\textrm{零博士}}
[1, 0, 0]\xrightarrow{\textrm{壹博士}}[0, 0, 0]\xrightarrow[\textrm{跳过}]{\textrm{零博士}}[0, 0, 0].
$$
记$S(n)$为使零博士有必胜策略所需的最小跳过回合数。

例如，$S(2) = 2$，$S(5) = 17$，$S(10) = 64$。

求$S(10^5)$。

---