Solution

Answer: 426334056

Let $P(n)$ be the survivor of the alternating elimination process.

We are given:

$P(1)=1$
$P(9)=6$
$P(1000)=510$
$S(n)=\sum_{k=1}^n P(k)$
$S(1000)=268271$

We must compute:

$$S(10^{18}) \bmod 987654321$$

1. Mathematical analysis

Step 1: Recurrence for $P(n)$

After the first left-to-right pass on $1,2,\dots,n$:

all odd numbers are removed,
the remaining list is

$$2,4,6,\dots,2\left\lfloor \frac n2 \right\rfloor$$

Divide everything by $2$. The remaining problem becomes the same elimination process, but starting from the opposite direction.

If we denote the survivor by $P(n)$, then the classical elimination-game recurrence is:

$$P(n)=2\left(1+\left\lfloor\frac n2\right\rfloor-P!\left(\left\lfloor\frac n2\right\rfloor\right)\right)$$

with base case

$$P(1)=1.$$

Equivalently, for $n\ge1$,

$$P(2n)=P(2n+1)=2(n+1-P(n)).$$

This immediately explains why consecutive odd/even pairs have equal values.

Step 2: Deriving a recurrence for $S(n)$

Define

$$A(n)=\sum_{k=1}^n P(2k).$$

Using the recurrence:

$$P(2k)=2(k+1-P(k)),$$

$$A(n) =\sum_{k=1}^n 2(k+1-P(k)).$$

Therefore

$$A(n) =2\sum_{k=1}^n k + 2n -2S(n).$$

Since

$$\sum_{k=1}^n k=\frac{n(n+1)}2,$$

we get

$$A(n)=n(n+1)+2n-2S(n) =n^2+3n-2S(n).$$

Step 3: Express $S(2n)$ and $S(2n+1)$

Because

$$P(2k-1)=P(2k),$$

we have

$$S(2n) =1+2\sum_{k=1}^{n-1}P(2k)+P(2n).$$

That is,

$$S(2n)=1+2A(n)-P(2n).$$

Substitute the formulas:

$$A(n)=n^2+3n-2S(n),$$

and

$$P(2n)=2(n+1-P(n)).$$

After simplification:

$$\boxed{ S(2n)=2n^2+4n-1-2S(n)-2S(n-1) }$$

Similarly,

$$S(2n+1)=S(2n)+P(2n+1).$$

Since $P(2n+1)=P(2n)$,

$$S(2n+1)=1+2A(n),$$

hence

$$\boxed{ S(2n+1)=2n^2+6n+1-4S(n) }$$

These recurrences reduce the argument by half each time, so the complexity is only $O(\log n)$.

2. Python implementation

from functools import lru_cache

MOD = 987654321

@lru_cache(None)
def S(n):
    # Base cases
    if n <= 0:
        return 0
    if n == 1:
        return 1

    # Even case: n = 2m
    if n % 2 == 0:
        m = n // 2
        return (
            2 * m * m
            + 4 * m
            - 1
            - 2 * S(m)
            - 2 * S(m - 1)
        ) % MOD

    # Odd case: n = 2m + 1
    else:
        m = n // 2
        return (
            2 * m * m
            + 6 * m
            + 1
            - 4 * S(m)
        ) % MOD

answer = S(10**18)
print(answer)

3. Code walkthrough

Memoization

@lru_cache(None)

stores previously computed values of $S(n)$, ensuring each subproblem is solved once.

Because every recurrence halves the argument, there are only about 60 distinct recursive levels for $10^{18}$.

Base cases

if n <= 0:
    return 0
if n == 1:
    return 1

These correspond to:

$$S(0)=0,\qquad S(1)=1.$$

Even case

if n % 2 == 0:
    m = n // 2

Then $n=2m$, and we apply:

$$S(2m)=2m^2+4m-1-2S(m)-2S(m-1).$$

Odd case

else:
    m = n // 2

Then $n=2m+1$, and we apply:

$$S(2m+1)=2m^2+6m+1-4S(m).$$

4. Verification on the given examples

The program reproduces:

$$P(9)=6,$$

and

$$S(1000)=268271,$$

matching the problem statement exactly.

The recursion depth is tiny ($<100$), so computation for $10^{18}$ is instantaneous.

After evaluating:

$$S(10^{18}) \bmod 987654321,$$

we obtain:

Answer: 426334056

Project Euler Problem 539