Detailed mathematical approach

Problem Summary

For each positive integer \(n\), let \(t(n)\) be the smallest offset \(k\) such that the DistribuNim II position consisting of \(n\) piles of size \(n\) and one additional pile of size \(n+k\) is a losing position. The problem asks for

$S(N)=\sum_{n=1}^{2^N} t(n)\pmod{900497239}.$

A direct search over game states is hopeless for large \(N\). The efficient solution therefore avoids game-tree exploration and instead uses a closed formula for each \(t(n)\), followed by an exact summation over bit-length blocks.

Mathematical Approach

The key fact used by the optimized solution is that the losing offset is controlled by the low bits of \(n^2\).

Step 1: Closed Form for \(t(n)\)

Let

$m=\lfloor \log_2 n \rfloor+1,\qquad 2^{m-1}\le n<2^m.$

Define

$\varepsilon(n)=\begin{cases} 0, & n\text{ even},\\ 2^m-1, & n\text{ odd}. \end{cases}$

Then the implementations use the identity

$t(n)=\bigl(\varepsilon(n)-n^2\bigr)\bmod 2^m.$

Equivalently,

$t(n)=\begin{cases} (-n^2)\bmod 2^m, & n\text{ even},\\ (-n^2-1)\bmod 2^m, & n\text{ odd}. \end{cases}$

So once the bit-length \(m\) is known, we only need the lowest \(m\) bits of \(n^2\).

Step 2: Sum by Fixed Bit-Length

For each \(m\ge 1\), define the block sum

$B_m=\sum_{n=2^{m-1}}^{2^m-1} t(n).$

If \(n=2^r\), then \(n\) is even and \(n^2=2^{2r}\) is divisible by \(2^{r+1}\), so \(t(2^r)=0\). Therefore the endpoint \(n=2^N\) contributes nothing, and

$S(N)=\sum_{m=1}^{N} B_m.$

Now write

$n=2^{m-1}+j,\qquad 0\le j<2^{m-1}.$

Then

$n^2=(2^{m-1}+j)^2\equiv j^2 \pmod{2^m},$

because both \(2^{2m-2}\) and \(2^m j\) are multiples of \(2^m\). For \(m\ge 2\), the number \(2^{m-1}\) is even, so \(n\) and \(j\) have the same parity. Hence

$t(2^{m-1}+j)=\begin{cases} (-j^2)\bmod 2^m, & j\text{ even},\\ (-j^2-1)\bmod 2^m, & j\text{ odd}. \end{cases}$

Step 3: Evaluate One Whole Block

Split the block into even and odd offsets:

$j=2u\quad\text{or}\quad j=2u+1,\qquad 0\le u<2^{m-2}.$

Then the even contribution is built from residues of \(4u^2\), while the odd contribution is built from residues of \(4u(u+1)+1\). Summing those two parity classes over a complete block gives exact formulas

$B_{2k}=4^{2k-1}+2\cdot 8^{k-1}-2^{2k},\qquad k\ge 1,$

$B_{2k+1}=4^{2k}+8^k-2^{2k+1},\qquad k\ge 0.$

The first few values are

$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64,\qquad B_5=288,$

which already shows the geometric structure that the code exploits.

Step 4: Sum the Block Formulas

Every block contributes a \(4^{m-1}\) term, so

$\sum_{m=1}^{N} 4^{m-1}=\frac{4^N-1}{3}.$

The \(8\)-power corrections come in adjacent pairs. Block \(2k+1\) contributes \(8^k\), and block \(2k+2\) contributes \(2\cdot 8^k\), so one complete pair contributes \(3\cdot 8^k\). If

$K=\left\lfloor \frac{N}{2}\right\rfloor,$

then the total \(8\)-power contribution is

$\frac{3(8^K-1)}{7}+\mathbf{1}_{N\text{ odd}}\,8^K.$

The subtractive pieces add up to

$\sum_{m=1}^{N}2^m=2^{N+1}-2.$

Therefore

$\boxed{S(N)=\frac{4^N-1}{3}+\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ odd}}\,8^{\lfloor N/2\rfloor}-(2^{N+1}-2)\pmod{900497239}.}$

Step 5: Worked Example

Take \(n=6\). Here \(m=3\) because \(4\le 6<8\). Since \(6\) is even,

$t(6)=(-6^2)\bmod 8=(-36)\bmod 8=4.$

Take \(n=5\). Again \(m=3\), but now \(5\) is odd, so

$t(5)=(-5^2-1)\bmod 8=(-26)\bmod 8=6.$

For \(N=4\), the block totals are

$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64,$

hence

$S(4)=0+2+16+64=82.$

This matches the direct sum of \(t(n)\) for \(1\le n\le 16\).

How the Code Works

The C++, Python, and Java implementations all follow the same fast path. First they compute the modular inverses needed for the fractions \(1/3\) and \(1/7\). Next they evaluate \(4^N\), \(8^{\lfloor N/2\rfloor}\), and \(2^{N+1}\) with fast modular exponentiation. Those three powers are then assembled into

$\text{sumA}=\frac{4^N-1}{3},\qquad \text{sumB}=\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ odd}}\,8^{\lfloor N/2\rfloor},\qquad \text{sumC}=2^{N+1}-2,$

and the final answer is \(\text{sumA}+\text{sumB}-\text{sumC}\) modulo \(900497239\). The C++ implementation also keeps small-scale validation logic: it compares the closed form with direct summation for small \(N\) and checks the first few losing offsets against brute force, but the production result is obtained entirely from the closed formula.

Complexity Analysis

The optimized method uses only a constant number of modular exponentiations, so the running time is \(O(\log N)\) and the memory usage is \(O(1)\). By contrast, the defining sum already has \(2^N\) terms before considering any game-state search, so the closed form is what makes the problem tractable.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=900
2. Impartial combinatorial games: Wikipedia - Impartial game
3. Modular arithmetic: Wikipedia - Modular arithmetic
4. Quadratic residues: Wikipedia - Quadratic residue
5. Geometric series: Wikipedia - Geometric series
6. Modular exponentiation: Wikipedia - Modular exponentiation