Solution

Answer: 216737278

Let

$$(a,b,c),\qquad 0<a<b<c$$

be a position of the modified Nim game where moves that create two equal heaps are forbidden.

We must compute

$$F(N)=\sum (a+b+c)$$

over all losing positions (P-positions) with $0<a<b<c<N$, and finally output the last $9$ digits of $F(10^{18})$.

Mathematical analysis

1. Characterising the losing positions

The key observation is that the game becomes ordinary Nim after a simple shift.

Define

$$x=a+1,\qquad y=b+1,\qquad z=c+1.$$

Then the rule “you may not make two heaps equal” translates into the fact that the terminal positions are exactly those with one coordinate equal to $1$ and the others equal to $2,3$ in shifted form.

Experimenting with small states (and proving inductively using the Sprague–Grundy recurrence) gives the exact criterion:

$$(a,b,c)\text{ is losing} \iff (a+1)\oplus(b+1)\oplus(c+1)=0,$$

where $\oplus$ denotes bitwise XOR.

So if we set

$$x=a+1,\ y=b+1,\ z=c+1,$$

then the losing positions are exactly the distinct positive triples satisfying

$$x\oplus y\oplus z=0.$$

Because $z=x\oplus y$, once $x,y$ are chosen, $z$ is determined.

2. Converting the sum

We need

$$0<a<b<c<N.$$

After shifting:

$$2\le x<y<z\le N.$$

The quantity being summed is

$$a+b+c=(x-1)+(y-1)+(z-1)=x+y+z-3.$$

So the task reduces to summing $x+y+z-3$ over all unordered distinct triples with

$$x\oplus y\oplus z=0.$$

3. Ordered triples instead of unordered triples

It is easier to count ordered triples.

For XOR-zero triples, equality cannot occur unless all three are equal, and in our range ($\ge2$) that is impossible. Hence every unordered triple corresponds to exactly $6$ ordered triples.

Therefore:

$$F(N) = \frac{ \sum_{\text{ordered}} (x+y+z)-3\cdot(#\text{ordered}) }{6}.$$

4. Digit DP over binary bits

We need to count ordered triples satisfying

$$x\oplus y=z,$$

with upper bounds.

This is a standard binary digit-DP:

process bits from most significant to least significant,
maintain “tightness” flags for whether we are still equal to the upper bounds,
at each bit choose bits of $x$ and $y$,
the bit of $z$ is forced:

$$z_i=x_i\oplus y_i.$$

The DP simultaneously accumulates:

the number of valid triples,
the total sum of all $x$,
the total sum of all $y$,
the total sum of all $z$.

Finally we apply inclusion–exclusion to enforce

$$x,y,z\ge2.$$

The complexity is only $O(\log N)$.

Python implementation

MOD = 10**9

def dp_count_sum(A: int, B: int, C: int):
    """
    Count triples (x,y,z) such that:
        0 <= x <= A
        0 <= y <= B
        z = x XOR y
        0 <= z <= C

    Returns:
        (count, total_sum_xyz)
    """

    if A < 0 or B < 0 or C < 0:
        return 0, 0

    bits = max(A, B, C).bit_length()
    if bits == 0:
        bits = 1

    # state = (tightA, tightB, tightC)
    count = [0] * 8
    sx = [0] * 8
    sy = [0] * 8
    sz = [0] * 8

    count[7] = 1  # initially all tight

    for p in range(bits - 1, -1, -1):

        bitA = (A >> p) & 1
        bitB = (B >> p) & 1
        bitC = (C >> p) & 1

        value = 1 << p

        ncount = [0] * 8
        nsx = [0] * 8
        nsy = [0] * 8
        nsz = [0] * 8

        for state in range(8):

            cnt = count[state]
            if cnt == 0:
                continue

            tightA = (state >> 2) & 1
            tightB = (state >> 1) & 1
            tightC = state & 1

            for xb in (0, 1):

                if tightA and xb > bitA:
                    continue

                ntA = 1 if (tightA and xb == bitA) else 0

                for yb in (0, 1):

                    if tightB and yb > bitB:
                        continue

                    ntB = 1 if (tightB and yb == bitB) else 0

                    zb = xb ^ yb

                    if tightC and zb > bitC:
                        continue

                    ntC = 1 if (tightC and zb == bitC) else 0

                    ns = (ntA << 2) | (ntB << 1) | ntC

                    ncount[ns] += cnt

                    nsx[ns] += sx[state] + cnt * xb * value
                    nsy[ns] += sy[state] + cnt * yb * value
                    nsz[ns] += sz[state] + cnt * zb * value

        count = ncount
        sx = nsx
        sy = nsy
        sz = nsz

    total_count = sum(count)
    total_sum = sum(sx) + sum(sy) + sum(sz)

    return total_count, total_sum

def F(N: int) -> int:
    """
    Sum of a+b+c over all losing positions:
        0 < a < b < c < N
    """

    L = N

    ordered_count = 0
    ordered_sum = 0

    # Inclusion-exclusion to enforce x,y,z >= 2
    for mask in range(8):

        A = 1 if (mask & 1) else L
        B = 1 if (mask & 2) else L
        C = 1 if (mask & 4) else L

        cnt, sm = dp_count_sum(A, B, C)

        if mask.bit_count() % 2 == 0:
            ordered_count += cnt
            ordered_sum += sm
        else:
            ordered_count -= cnt
            ordered_sum -= sm

    # Convert back from x,y,z to a,b,c:
    # a+b+c = x+y+z - 3

    return (ordered_sum - 3 * ordered_count) // 6

# Verification
assert F(8) == 42
assert F(128) == 496062

answer = F(10**18) % MOD
print(answer)

Code walkthrough

`dp_count_sum(A,B,C)`

This performs a bitwise digit DP.

At each bit:

choose a bit for $x$,
choose a bit for $y$,
compute the bit of $z$ as XOR,
maintain tightness conditions.

The DP stores:

how many triples exist,
the accumulated sums of $x$, $y$, and $z$.

Inclusion–exclusion

We first count triples with coordinates allowed to be $0$ or $1$, then remove those violating $x,y,z\ge2$.

This is done by the 8 masks:

$${x\le1},{y\le1},{z\le1}.$$

Division by 6

We counted ordered triples.

Each unordered triple appears exactly $6$ times because the coordinates are distinct.

So we divide by $6$.

Verification

The program reproduces the examples:

$$F(8)=42$$

and

$$F(128)=496062.$$

The DP runs in logarithmic time in $N$, so $N=10^{18}$ is trivial.

The computed value is:

$$F(10^{18}) \bmod 10^9 = 216737278.$$

Answer: 216737278

Project Euler Problem 488