Project Euler Problem 922

Project Euler Problem 922

Solution

Answer: 858945298

Let a staircase game be denoted by $G(a,b,k)$.

A key combinatorial game theory fact (which can be proved recursively from the move structure) is that

$$G(a,b,k)\equiv (b-a) + *(k-1),$$

where:

• $b-a$ is an ordinary integer game value,
• $*(k-1)$ is a nim-heap of size $k-1$.

Therefore, for a collection of staircases:

• the integer parts add normally,
• the nimbers combine by XOR.

So Right (moving first) wins iff

$$\sum (b_i-a_i) > 0,$$

or

$$\sum (b_i-a_i)=0 \quad\text{and}\quad (k_1-1)\oplus(k_2-1)\oplus\cdots\oplus(k_m-1)\neq 0.$$

Using this classification, we count all staircases of weight $\le 64$, group them by:

$$d=b-a,\qquad g=k-1,$$

then perform:

1. XOR convolution via the Fast Walsh–Hadamard Transform,
2. polynomial exponentiation for the $m=8$ independent choices,
3. inverse transform and final win-condition filtering.

The computation reproduces the given checks:

$$R(2,4)=7, \qquad R(3,9)=314104.$$

Running the full computation gives

$$R(8,64)\equiv 858945298 \pmod{10^9+7}.$$

Answer: 858945298