Detailed mathematical approach

Problem Summary

We consider three distinct heap sizes \(a\lt b\lt c\). A legal move decreases exactly one heap to a smaller nonnegative size, after which the three heap sizes are reordered and must still be distinct. Let \(\mathcal{P}\) denote the set of losing positions for this game.

Define \(\mathcal{P}_N=\{(a,b,c)\in\mathcal{P}: 0\lt a\lt b\lt c\lt N\}\).

The quantity to compute is

$F(N)=\sum_{(a,b,c)\in\mathcal{P}_N}(a+b+c)\pmod{10^9}.$

A direct search over all triples below \(N\) is only feasible for tiny bounds. The implementation avoids that cubic search space by using a structural parametrization of all losing positions and then summing each block in closed form.

Mathematical Approach

The main game-specific fact used by the implementation is that every losing position belongs to a unique dyadic block indexed by

$p=2^k-1,\qquad k\ge 1,$

and inside that block the losing triples are exactly

$c=p+n,\qquad b=p+t,\qquad a=(n\oplus t)-1,$

with

$1\le n\le p,\qquad 0\le t\lt n.$

Here \(\oplus\) is bitwise XOR. Because \(c=p+n\) lies in the interval \(p+1\le c\le 2p\), the largest heap chooses the block uniquely, so different values of \(k\) never overlap.

Step 1: Restrict the Block to the Bound \(N\)

To contribute to \(F(N)\), the largest heap must satisfy \(c\lt N\). Since \(c=p+n\), this becomes

$p+n\lt N\iff n\le N-1-p.$

Therefore the relevant range of \(n\) is

$1\le n\le m,\qquad m=\min\{p,\ N-1-p\}.$

For each such \(n\), the parameter \(t\) runs through \(0,1,\dots,n-1\), which automatically ensures \(b\lt c\).

Step 2: Sum the Contribution of One Block

Fix a block parameter \(p\). For a fixed \(n\), summing over all allowed \(t\) gives

$a+b+c=(n\oplus t)-1+(p+t)+(p+n).$

Define the XOR row sum

$X(n)=\sum_{t=0}^{n-1}(n\oplus t).$

Then

$\sum_{t=0}^{n-1}(a+b+c)=X(n)+\sum_{t=0}^{n-1}t+n^2+n(2p-1).$

Because \(\sum_{t=0}^{n-1}t=\frac{n(n-1)}{2}\), the raw contribution of the block is

$\sum_{n=1}^{m}\left(X(n)+\frac{n(n-1)}{2}+n^2+(2p-1)n\right).$

So the whole problem reduces to four standard sums:

$\sum_{n=1}^{m}X(n),\qquad \sum_{n=1}^{m}n,\qquad \sum_{n=1}^{m}n^2,\qquad \sum_{n=1}^{m}\frac{n(n-1)}{2}.$

Step 3: Closed Forms for the Polynomial Terms

The ordinary arithmetic sums are classical:

$\sum_{n=1}^{m}n=\frac{m(m+1)}{2},$

$\sum_{n=1}^{m}n^2=\frac{m(m+1)(2m+1)}{6},$

$\sum_{n=1}^{m}\frac{n(n-1)}{2}=\frac{m(m+1)(m-1)}{6}.$

The implementation evaluates these formulas exactly by dividing by \(2\) and \(3\) before modular multiplication, so everything remains valid modulo \(10^9\).

Step 4: Fast Evaluation of the XOR Prefix Sum

Set \(X(0)=0\) and define

$S(n)=\sum_{i=0}^{n-1}X(i).$

Then the needed XOR contribution is simply \(\sum_{n=1}^{m}X(n)=S(m+1)\).

To evaluate \(S\) quickly, write

$n=2^m+r,\qquad 0\le r\lt 2^m,$

and let \(p=2^m\). For \(0\le r\lt p\), split the definition of \(X(p+r)\) into two ranges:

$X(p+r)=\sum_{t=0}^{p-1}((p+r)\oplus t)+\sum_{u=0}^{r-1}((p+r)\oplus(p+u)).$

In the first sum the top bit stays set, so \((p+r)\oplus t=p+(r\oplus t)\). As \(t\) runs through \(0,\dots,p-1\), the values \(r\oplus t\) are a permutation of \(0,\dots,p-1\). Hence

$\sum_{t=0}^{p-1}((p+r)\oplus t)=p^2+\sum_{v=0}^{p-1}v=p^2+\frac{p(p-1)}{2}=\frac{p(3p-1)}{2}.$

In the second sum the top bit cancels, so \((p+r)\oplus(p+u)=r\oplus u\). Therefore

$X(p+r)=C_m+X(r),\qquad C_m=\frac{2^m(3\cdot 2^m-1)}{2}.$

Summing this identity over \(r\) gives the key recursion

$\boxed{S(2^m+r)=S(2^m)+r\,C_m+S(r).}$

For powers of two we get

$S(2^{m+1})=2S(2^m)+2^mC_m,$

so the implementation precomputes \(S(2^m)\) and \(C_m\) once and then evaluates any \(S(n)\) in \(O(\log n)\) recursive steps.

Step 5: Correct the Auxiliary States with \(a=0\)

The parametrization above also produces states whose smallest heap is \(a=0\). These states appear naturally in the game graph, but they are not part of \(F(N)\), which only sums \(0\lt a\lt b\lt c\).

We have \(a=0\) exactly when

$n\oplus t=1,$

so the candidate is \(t=n\oplus 1\). This is inside the legal range \(0\le t\lt n\) if and only if \(n\) is odd, in which case \(t=n-1\). Thus each odd \(n\) contributes exactly one invalid triple.

For odd \(n\), the excluded sum equals

$0+(p+n-1)+(p+n)=2p+2n-1.$

If

$q=\left\lfloor\frac{m+1}{2}\right\rfloor,$

then the odd integers in \([1,m]\) are \(1,3,\dots,2q-1\), so

$\sum_{\substack{1\le n\le m\\ 2\nmid n}}1=q,\qquad \sum_{\substack{1\le n\le m\\ 2\nmid n}}n=q^2.$

Therefore the correction term for one block is

$\boxed{(2p-1)q+2q^2.}$

Step 6: Final Block Formula

Combining the raw block sum with the odd-\(n\) correction, the contribution of block \(p=2^k-1\) is

$\begin{aligned} B(p,m)=&\ S(m+1)+\frac{m(m+1)(m-1)}{6}+\frac{m(m+1)(2m+1)}{6}\\ &+(2p-1)\frac{m(m+1)}{2}-\left((2p-1)q+2q^2\right), \end{aligned}$

where

$m=\min\{p,\ N-1-p\},\qquad q=\left\lfloor\frac{m+1}{2}\right\rfloor.$

Hence the whole answer is

$\boxed{F(N)=\sum_{\substack{k\ge 1\\ 2^k\lt N}} B(2^k-1,\ \min\{2^k-1,\ N-2^k\})\pmod{10^9}.}$

After the structural theorem about losing positions, everything else is pure arithmetic.

Worked Example: \(F(8)=42\)

For \(N=8\), the only possible blocks are \(p=1\) and \(p=3\).

For \(p=1\), we have \(m=1\). The unique parametrized triple is \((0,1,2)\), so the entire block disappears after the \(a=0\) correction.

For \(p=3\), we have \(m=3\). First compute

$X(1)=1,\qquad X(2)=2+3=5,\qquad X(3)=3+2+1=6,$

hence

$\sum_{n=1}^{3}X(n)=12,\qquad \sum_{n=1}^{3}n=6,\qquad \sum_{n=1}^{3}n^2=14,\qquad \sum_{n=1}^{3}\frac{n(n-1)}{2}=4.$

The raw block total is

$12+14+4+(2\cdot 3-1)\cdot 6=12+14+4+30=60.$

Now \(q=\left\lfloor\frac{3+1}{2}\right\rfloor=2\), so the correction is

$(2\cdot 3-1)\cdot 2+2\cdot 2^2=10+8=18.$

Therefore

$F(8)=60-18=42,$

which matches the checkpoint used by the implementation. A second checkpoint is \(F(128)=496062\).

How the Implementation Works

The C++, Python, and Java implementations all follow the same plan. They enumerate the dyadic blocks \(p=2^k-1\) with \(p+1\lt N\), compute the cutoff \(m=\min\{p,N-1-p\}\), and add the closed-form block contribution modulo \(10^9\).

The only nontrivial subroutine is the evaluator for \(S(n)\). It uses the recursion above together with precomputed values at powers of two, so no block ever loops over all \(t\) or all \(n\). Because different blocks are independent, the outer accumulation can also be split across worker threads or processes.

Complexity Analysis

There are \(O(\log N)\) dyadic blocks because \(p=2^k-1\). Each block requires only a constant number of modular polynomial sums plus one evaluation of \(S(m+1)\), and the recursion for \(S\) has depth \(O(\log N)\). Therefore the total running time is

$O((\log N)^2),$

and the memory usage is \(O(\log N)\) for the precomputed tables of powers of two. This is exponentially smaller than any direct exploration of all triples below \(N\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=488
2. Nim and losing positions: Wikipedia — Nim
3. XOR and bitwise algebra: Wikipedia — XOR
4. Powers of two and binary intervals: Wikipedia — Power of two
5. Berlekamp, Conway, Guy. Winning Ways for your Mathematical Plays.