Project Euler Problem 900
Two players play a game with at least two piles of stones.
Solution
Answer: 646900900
A key observation is that the special position
$$(n,n,\dots,n,n+k)$$
(with $n$ copies of $n$ and one extra pile $n+k$) has a surprisingly simple closed form.
Let
$$p = 2^{\lfloor \log_2 n \rfloor + 1},$$
the smallest power of two strictly greater than $n$.
Then
$$t(n)\equiv -n^2-(n\bmod 2)\pmod p,$$
with $0\le t(n)<p$.
This reproduces the given values:
- $t(1)=0$
- $t(2)=0$
- $t(3)=2$
and gives the correct check:
$$S(10)=361522.$$
Furthermore, the sequence
$$S(N)=\sum_{n=1}^{2^N} t(n)$$
satisfies the linear recurrence
$$S(n)=7S(n-1)-6S(n-2)-48S(n-3)+112S(n-4)-64S(n-5),$$
valid for $n\ge 6$.
Using the exact initial values (verified directly from the closed form) and iterating the recurrence modulo $900497239$ up to $N=10^4$ yields:
$$S(10^4)\equiv 646900900 \pmod{900497239}.$$
Therefore,
Answer: 646900900