Detailed mathematical approach

Problem Summary

In Divisor Nim, a move on a pile of size \(n\) chooses a proper divisor \(d\lt n\) and replaces the pile by \(n-d\). With three independent piles \((a,b,c)\), let \(S(N)\) be the number of winning starting triples with \(1\le a,b,c\le N\). The goal is to compute \(S(123456787654321)\) modulo \(1234567890\).

A direct search over all \(N^3\) triples is impossible. The key simplification is that the single-pile Sprague-Grundy value depends only on the exponent of 2 in the pile size, so the whole three-pile count becomes a short xor-based sum over valuation buckets.

Mathematical Approach

Let \(g(n)\) denote the Sprague-Grundy value of one pile of size \(n\), and let \(M=1234567890\). The problem is to count three-pile positions whose xor is nonzero.

Step 1: Reduce the three-pile game to Grundy values

Divisor Nim is an impartial normal-play game, so the Sprague-Grundy theorem applies. Therefore

$\text{the position }(a,b,c)\text{ is losing} \iff g(a)\oplus g(b)\oplus g(c)=0.$

Once the single-pile function \(g(n)\) is known, the rest of the problem is just counting how often each Grundy value appears among the integers from \(1\) to \(N\).

Step 2: Prove that \(g(n)=v_2(n)\)

Write

$n=2^e q,\qquad q\text{ odd},\qquad e=v_2(n).$

Any proper divisor of \(n\) has the form

$d=2^a b,\qquad 0\le a\le e,\qquad b\mid q,$

with \((a,b)\ne (e,q)\) because \(d\lt n\).

If \(a\lt e\), then

$n-d=2^a\left(2^{e-a}q-b\right).$

Here \(2^{e-a}q\) is even and \(b\) is odd, so the bracket is odd. Hence

$v_2(n-d)=a.$

If \(a=e\), then \(d=2^e b\) with \(b\lt q\), so

$n-d=2^e(q-b).$

Both \(q\) and \(b\) are odd, so \(q-b\) is a positive even number. Therefore

$v_2(n-d)>e.$

So a move from \(n\) can reach every valuation \(0,1,\dots,e-1\), can sometimes reach valuations larger than \(e\), but can never reach valuation \(e\) itself. In particular, for each \(0\le a\lt e\), choosing \(d=2^a q\) gives

$n-d=2^a q\left(2^{e-a}-1\right),$

and the factor \(2^{e-a}-1\) is odd, so \(v_2(n-d)=a\).

Now induct on \(n\). Every move goes to a smaller pile, so the reachable Grundy values are exactly the reachable valuations of smaller positions. They include \(0,1,\dots,e-1\), they do not include \(e\), and any larger values do not change the mex. Thus

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

For odd \(n\), this says \(g(n)=0\), which is consistent because every move from an odd pile lands on an even pile.

Step 3: Count how many integers have each Grundy value

Define

$C_k=\#\{x\in[1,N]:v_2(x)=k\}.$

The integers with \(v_2(x)\ge k\) are exactly the multiples of \(2^k\), so

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

Only finitely many buckets are nonzero. Once \(2^k>N\), the count vanishes, so only \(k\le \lfloor\log_2 N\rfloor\) matter.

Step 4: Count losing triples with xor zero

A starting triple is losing exactly when

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

If the first two valuations are \(i\) and \(j\), then the third must be \(i\oplus j\). Therefore the number of losing triples is

$L(N)=\sum_{i\ge 0}\sum_{j\ge 0} C_i\,C_j\,C_{i\oplus j}.$

The total number of triples is \(N^3\), so the winning count is

$S(N)=N^3-L(N),$

and the reported answer is \(S(N)\pmod{M}\).

Worked Example: \(N=10\)

For \(1\le x\le 10\), the buckets are

$C_0=5,\qquad C_1=3,\qquad C_2=1,\qquad C_3=1,$

coming from the sets

$\{1,3,5,7,9\},\quad \{2,6,10\},\quad \{4\},\quad \{8\}.$

Then

$L(10)=\sum_{i,j=0}^{3} C_i\,C_j\,C_{i\oplus j}=308.$

Since \(10^3=1000\), we obtain

$S(10)=1000-308=692,$

which matches the checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations do not explore game trees. Instead, they first count how many integers in \([1,N]\) have valuation \(0,1,2,\dots\) using repeated divisions by powers of 2, which realizes

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

They then run a double loop over the nonzero buckets. For each pair \((i,j)\), they compute \(k=i\oplus j\) and add the contribution \(C_iC_jC_k\) to the losing total modulo \(1234567890\). Finally, they compute \(N^3\bmod M\) and subtract the losing total modulo \(M\).

The C++ implementation also performs small sanity checks before the final large evaluation: it confirms the Grundy pattern on an initial range, checks the benchmark values \(S(10)=692\) and \(S(100)=735494\), and compares the closed-form count with a brute-force computation for a small input. The Python and Java implementations apply the same counting formula directly.

Complexity Analysis

There are only \(O(\log N)\) nonzero valuation buckets. Building the bucket counts takes \(O(\log N)\) time and \(O(\log N)\) memory. The xor-based counting stage uses a double loop over those buckets, so it costs \(O((\log N)^2)\) time. For the target input, a fixed table of 64 buckets is enough, so the practical running time is tiny.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=509
2. Sprague-Grundy theorem: Wikipedia — Sprague-Grundy theorem
3. \(p\)-adic valuation, especially the \(2\)-adic case: Wikipedia — p-adic valuation
4. Nim and xor structure: Wikipedia — Nim
5. Exclusive or: Wikipedia — Exclusive or