Solution

Answer: 151725678

Let $g(n)$ be the Sprague–Grundy value of a pile of size $n$.

A move consists of choosing a proper divisor $d\mid n$, $d<n$, and replacing $n$ by $n-d$.

For three piles, the position $(a,b,c)$ is losing iff

$$g(a)\oplus g(b)\oplus g(c)=0,$$

where $\oplus$ is bitwise XOR.

So the entire problem reduces to understanding $g(n)$.

1. Mathematical analysis

Step 1: Compute the Grundy values

Let $v_2(n)$ denote the exponent of $2$ in $n$, i.e.

$$n = 2^{v_2(n)} \cdot m \quad (m \text{ odd}).$$

We claim:

$$g(n)=v_2(n).$$

We prove this.

Step 2: Structure of the moves

Suppose

$$n = 2^k m,\qquad m\text{ odd}.$$

Every proper divisor $d$ of $n$ can be written as

$$d=2^t u,$$

where $0\le t\le k$, $u\mid m$.

The new pile size is

$$n-d.$$

We only care about its 2-adic valuation.

Reachability of smaller Grundy values

Take any $t<k$.

Choose

$$d = 2^t m.$$

Since $t<k$, this is a proper divisor of $n$.

Then

$$n-d =2^k m-2^t m =2^t m(2^{k-t}-1).$$

Because $2^{k-t}-1$ is odd,

$$v_2(n-d)=t.$$

So from a pile with valuation $k$, every smaller valuation

$0,1,\dots,k-1$ is reachable.

No move preserves valuation $k$

Write

$$n=2^k m,\qquad d=2^t u.$$

If $t<k$, then

$$n-d=2^t(\text{odd}),$$

so the valuation is exactly $t<k$.

If $t=k$, then

$$d=2^k u,$$

with $u\mid m$. Since $u<m$ for a proper divisor,

$$n-d = 2^k(m-u),$$

and $m-u$ is even (odd minus odd), hence

$$v_2(n-d)\ge k+1.$$

So valuation $k$ itself is never reachable.

Thus the reachable Grundy values are exactly

$${0,1,\dots,k-1}.$$

Therefore

$$g(n)=\operatorname{mex}{0,1,\dots,k-1}=k.$$

Hence

$$\boxed{g(n)=v_2(n)}.$$

2. Counting losing positions

Define

$$c_k = #{1\le x\le n : v_2(x)=k}.$$

These are the integers divisible by $2^k$ but not by $2^{k+1}$:

$$c_k = \left\lfloor \frac{n}{2^k}\right\rfloor - \left\lfloor \frac{n}{2^{k+1}}\right\rfloor.$$

A triple is losing iff

$$v_2(a)\oplus v_2(b)\oplus v_2(c)=0.$$

So the number of losing triples is

$$L = \sum_{i,j\ge0} c_i c_j c_{i\oplus j}.$$

Therefore

$$S(n)=n^3-L.$$

3. Python implementation

def S(n):
    # c[k] = count of numbers with v2(x) = k
    c = []
    k = 0

    while (1 << k) <= n:
        ck = n // (1 << k) - n // (1 << (k + 1))
        c.append(ck)
        k += 1

    # Count losing triples:
    # v2(a) xor v2(b) xor v2(c) = 0
    losing = 0

    for i, a in enumerate(c):
        for j, b in enumerate(c):
            x = i ^ j
            if x < len(c):
                losing += a * b * c[x]

    return n**3 - losing

# Check the examples
print(S(10))    # 692
print(S(100))   # 735494

# Required value
MOD = 1234567890
n = 123456787654321

print(S(n) % MOD)

4. Code walkthrough

Building the counts

ck = n // (1 << k) - n // (1 << (k + 1))

counts integers with exact 2-adic valuation $k$.

Example:

divisible by $2^k$
but not by $2^{k+1}$

Counting losing triples

$$i \oplus j \oplus k = 0,$$

then

$$k=i\oplus j.$$

So for each pair $(i,j)$, the required third valuation is uniquely determined.

The number of triples with those valuations is

$$c_i c_j c_{i\oplus j}.$$

Summing gives all losing positions.

Final result

All triples:

$$n^3.$$

Winning triples:

$$S(n)=n^3-L.$$

5. Verification

The program reproduces the given values:

$$S(10)=692,$$

$$S(100)=735494.$$

So the derivation is consistent.

For

$$n=123456787654321,$$

the computation gives:

$$S(n)\bmod 1234567890 = 151725678.$$

Answer: 151725678

Project Euler Problem 509