Project Euler Problem 899

Two players play a game with two piles of stones.

Project Euler Problem 899

Solution

Answer: 10784223938983273

Let $P(a,b)$ denote that the position with piles $(a,b)$ is losing for the player to move.

Assume $a\le b$.

A move chooses some $j$ with $1\le j\le a$, leaving

$$(a,b)\to (j,b-j).$$

(Indeed, if we remove $a-j$ stones from the smaller pile and $j$ from the larger pile, the total removed is $a$.)


Key characterization of losing positions

By induction on $a+b$, one finds:

$$P(a,b)\iff a<\operatorname{lowbit}(b+1),$$

where

$$\operatorname{lowbit}(n)=2^{v_2(n)}$$

is the largest power of $2$ dividing $n$.

Examples:

  • $b=7$: $\operatorname{lowbit}(8)=8$, so every $1\le a\le7$ is losing.
  • $b=11$: $\operatorname{lowbit}(12)=4$, so exactly $a=1,2,3$ are losing.

This matches the sample $L(7)=21$.


Counting losing positions

Fix the larger pile $b$, and let

$$t=\operatorname{lowbit}(b+1).$$

Then the losing positions with larger pile $b$ are exactly

$$a=1,2,\dots,t-1.$$

So:

  • if $t=b+1$ (i.e. $b+1$ is a power of $2$), the diagonal pair $(b,b)$ occurs once;
  • otherwise every pair contributes twice by symmetry.

Hence the contribution for fixed $b$ is

$$2(t-1)-[b+1\text{ is a power of }2].$$

Therefore

$$L(n) = \sum_{b=1}^n \left(2(\operatorname{lowbit}(b+1)-1)-[b+1\text{ power of }2]\right).$$

Let

$$F(N)=\sum_{k=1}^N \operatorname{lowbit}(k).$$

Then

$$L(n)=2(F(n+1)-1-n)-\lfloor \log_2(n+1)\rfloor .$$


Computing $F(N)$

For each power $2^m$, exactly every $2^m$-th integer contributes at least $2^m$, so

$$F(N)=\sum_{m\ge0} 2^m\left\lfloor \frac{N+2^m}{2^{m+1}}\right\rfloor .$$

Evaluating this for

$$n=7^{17}=232630513987207$$

gives

$$L(7^{17})=10784223938983273.$$

We can verify the formula on the given values:

  • $L(7)=21$
  • $L(49)=221$

both correct.

Answer: 10784223938983273