Detailed mathematical approach

Problem Summary

We consider ordered piles \((x,y)\) with

$1\le x \lt y \le N.$

In each move, a player subtracts a positive multiple of the smaller pile from the larger pile, and the result must remain nonnegative. The player who takes the last stone wins. The problem asks for the sum of \(x+y\) over all losing pairs with \(1\le x \lt y\le N\):

$S(N)=\sum (x+y).$

for the enormous value

$N=10^{16},$

with the final answer reported modulo

$7^{10}=282475249.$

Mathematical Approach

1) First isolate the easy winning cases.

If \(y\ge 2x\), then the larger pile contains at least two copies of the smaller one, so the current player has several legal Euclid-style subtractions and can force a win immediately. Likewise, if \(x\mid y\), the current player can reduce to a terminal multiple situation. Therefore the only subtle region is

$x \lt y \lt 2x,\qquad x\nmid y.$

2) Inside that strip there is only one move.

When \(x \lt y \lt 2x\), the only allowed multiple is exactly one copy of the smaller pile. So the game moves deterministically to

$ (x,y)\longrightarrow (y-x,x), $

after reordering the two piles. This is just one step of Euclid's algorithm.

3) Losing positions form a golden-ratio interval.

Write \(y=x+d\) with

$1\le d \lt x.$

By the previous step, \((x,x+d)\) is losing exactly when \((d,x)\) is winning. Inductively, the losing positions are characterized by the sharp Beatty boundary

$x \lt y \le \lfloor \varphi x\rfloor,$

where

$\varphi=\frac{1+\sqrt5}{2}.$

Equivalently, for a fixed \(x\), the admissible differences are

$1\le d\le a_x,\qquad a_x=\left\lfloor\frac{x}{\varphi}\right\rfloor.$

The equality of the two forms comes from

$\varphi=1+\frac{1}{\varphi},\qquad \lfloor \varphi x\rfloor=x+\left\lfloor \frac{x}{\varphi}\right\rfloor.$

4) Convert the weighted sum to a double sum.

For each fixed \(x\), the losing values are

$y=x+1,\ x+2,\ \dots,\ x+a_x,$

unless the global bound \(y\le N\) truncates them. Therefore

$S(N)=\sum_{x=1}^{N}\sum_{d=1}^{\min(a_x,N-x)}(x+(x+d))$

or

$S(N)=\sum_{x=1}^{N}\sum_{d=1}^{\min(a_x,N-x)}(2x+d).$

5) Prefix-tail split.

Define the cutoff

$c=\left\lfloor\frac{N+1}{\varphi}\right\rfloor.$

If \(x\le c\), then the full losing interval still fits below \(N\), because \(x+a_x\le N\). If \(x\gt c\), the interval is cut short by the ceiling \(N\). Hence

$S(N)=S_{\text{pref}}+S_{\text{tail}}.$

6) The prefix depends on three Beatty sums.

For \(x\le c\), the inner sum is

$\sum_{d=1}^{a_x}(2x+d)=2x\,a_x+\frac{a_x(a_x+1)}{2}.$

Now define

$G(n)=\sum_{k=1}^{n} a_k,\qquad P(n)=\sum_{k=1}^{n} k\,a_k,\qquad Q(n)=\sum_{k=1}^{n} a_k^2.$

Then

$S_{\text{pref}}=\sum_{x=1}^{c}\left(2x\,a_x+\frac{a_x(a_x+1)}{2}\right)=\frac{4P(c)+Q(c)+G(c)}{2}.$

7) Why \(G,P,Q\) can be computed recursively.

Let

$m=\left\lfloor\frac{n}{\varphi}\right\rfloor.$

Classical Beatty partition identities allow us to rewrite the sums up to \(n\) in terms of the same sums up to \(m\). The code uses the exact recurrences

$G(n)=nm-\frac{m(m+1)}{2}-G(m),$

$Q(n)=nm^2-2\sum_{k=1}^{m}k^2-2P(m)+\frac{m(m+1)}{2}+G(m),$

$P(n)=\frac{nm(n+1)}{2}-\frac{\left(\sum_{k=1}^{m}k^2+2P(m)+Q(m)+\frac{m(m+1)}{2}+G(m)\right)}{2}.$

Each recursive step replaces \(n\) by approximately \(n/\varphi\), so the depth is only logarithmic.

8) The tail becomes an ordinary polynomial sum.

For \(x\gt c\), the upper limit is no longer \(a_x\), but \(N-x\). So the inner sum becomes

$\sum_{d=1}^{N-x}(2x+d)=2x(N-x)+\frac{(N-x)(N-x+1)}{2}.$

Summing this over \(x=c+1,\dots,N\) reduces the tail to combinations of

$\sum x,\qquad \sum x^2,$

which the code evaluates in closed form.

9) Worked example \(N=10\).

The losing pairs are

$(2,3),(3,4),(4,5),(4,6),(5,6),(5,7),(5,8),(6,7),(6,8),(6,9),$

$(7,8),(7,9),(7,10),(8,9),(8,10),(9,10).$

Their weighted sum is

$S(10)=211,$

which matches the checkpoint in the program.

Algorithm

1) Use the golden-ratio characterization of losing positions.

2) Split the total sum at \(c=\lfloor (N+1)/\varphi\rfloor\).

3) Evaluate the prefix via the recursive Beatty sums \(G,P,Q\).

4) Evaluate the tail via polynomial formulas for \(\sum x\) and \(\sum x^2\).

5) Do the same computation modulo \(7^{10}\) for the final output.

Complexity Analysis

Because each Beatty recursion step shrinks \(n\) to roughly \(n/\varphi\), the depth is

$O(\log N).$

Each level performs only constant-time big-integer or modular arithmetic, so the whole method is extremely fast even for \(N=10^{16}\).

Checks And Final Result

The code checks

$S(10)=211,\qquad S(10^4)=230312207313.$

It also verifies that exact arithmetic and arithmetic modulo \(7^{10}\) agree for \(N=10^6\).

For the target value

$N=10^{16},$

the final answer modulo \(7^{10}\) is

$54672965.$

Further Reading

1. Problem page: https://projecteuler.net/problem=325
2. Beatty sequences: https://en.wikipedia.org/wiki/Beatty_sequence
3. Euclid-type impartial games: https://en.wikipedia.org/wiki/Euclid's_algorithm#Game_of_Euclid