Detailed mathematical approach

Problem Summary

Start with the ordered list \(1,2,\dots,n\). In the first sweep, moving from left to right, remove every other surviving entry, so the first, third, fifth, and so on disappear. In the next sweep, move from right to left on the remaining list and again remove every other entry. Keep alternating directions until only one number remains; call that survivor \(P(n)\).

The problem asks for the prefix sum

$S(n)=\sum_{i=1}^{n}P(i)$

at

$n=10^{18},$

with the final result taken modulo

$M=987654321.$

Mathematical Approach

The decisive observation is that one left-to-right sweep immediately shrinks the list to roughly half its size. The only extra complication is that the next sweep starts from the opposite end, and that change can be handled by a simple mirror argument.

Step 1: Describe the first sweep

Let

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

After the first left-to-right elimination, the surviving values are exactly

$2,4,6,\dots,2m.$

Dividing all surviving entries by \(2\) produces the reduced list

$1,2,3,\dots,m.$

So the original problem on size \(n\) becomes a smaller problem on size \(m\), except that the next elimination pass now starts from the right rather than the left.

Because both \(2m\) and \(2m+1\) leave the same even survivors after the first sweep, we already know that

$P(2m)=P(2m+1).$

Step 2: Use mirror symmetry for the reversed direction

Consider the reduced list \(1,2,\dots,m\). A game that starts from the right is the mirror image of a game that starts from the left. Under the reflection

$j\longmapsto m+1-j,$

the survivor position of the right-start process is the complement of the survivor position of the left-start process.

Therefore the survivor index on \(1,\dots,m\) when the next sweep begins on the right is

$m+1-P(m).$

Undoing the earlier factor of \(2\) gives the survivor in the original list:

$\boxed{P(n)=2\left(m+1-P(m)\right),\qquad m=\left\lfloor\frac{n}{2}\right\rfloor,\ n\ge 2.}$

Together with the base case

$P(1)=1,$

this determines the survivor for every \(n\).

Step 3: Pair consecutive values

Since \(2m\) and \(2m+1\) share the same value of \(\lfloor n/2\rfloor\), the recurrence shows that they also share the same survivor:

$P(2m)=P(2m+1)=2\left(m+1-P(m)\right).$

This pairing is the main simplification for the sum. Instead of treating every term separately, we can combine the contribution of each pair \((2m,2m+1)\) into one formula.

Step 4: Derive the prefix-sum recurrences

Define

$S(n)=\sum_{i=1}^{n}P(i),\qquad S(0)=0,\qquad S(1)=1.$

For an odd upper bound \(n=2m+1\), group the equal pairs:

$\begin{aligned} S(2m+1) &=1+\sum_{k=1}^{m}\bigl(P(2k)+P(2k+1)\bigr)\\ &=1+\sum_{k=1}^{m}4\left(k+1-P(k)\right)\\ &=1+4\sum_{k=1}^{m}(k+1)-4\sum_{k=1}^{m}P(k). \end{aligned}$

Since

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

we obtain

$\boxed{S(2m+1)=1+2m(m+3)-4S(m).}$

For an even upper bound, subtract the last term of the odd case:

$\begin{aligned} S(2m) &=S(2m+1)-P(2m+1)\\ &=1+2m(m+3)-4S(m)-2\left(m+1-P(m)\right). \end{aligned}$

Simplifying gives

$\boxed{S(2m)=2m^2+4m-1-4S(m)+2P(m).}$

Step 5: Why divide-and-conquer is enough

Both recurrences replace \(n\) by \(\lfloor n/2\rfloor\). Starting from \(10^{18}\), repeated halving reaches \(1\) after only about sixty recursive levels.

So the algorithm only needs arguments along the short chain

$n,\left\lfloor\frac{n}{2}\right\rfloor,\left\lfloor\frac{n}{4}\right\rfloor,\left\lfloor\frac{n}{8}\right\rfloor,\dots.$

Once these states are memoized, the full problem size becomes easy to handle.

Worked Example: \(n=9\)

The elimination process is visible directly:

$1,2,3,4,5,6,7,8,9\ \longrightarrow\ 2,4,6,8\ \longrightarrow\ 2,6\ \longrightarrow\ 6.$

Hence

$P(9)=6.$

The recurrence gives the same answer. Since \(m=\lfloor 9/2\rfloor=4\),

$P(9)=2\left(5-P(4)\right).$

Now \(P(4)=2\), so \(P(9)=2(5-2)=6\).

The first nine survivor values are

$P(1),\dots,P(9)=1,2,2,2,2,4,4,6,6,$

therefore

$S(9)=29.$

The odd recurrence confirms this:

$S(9)=1+2\cdot 4\cdot 7-4S(4)=1+56-4\cdot 7=29.$

How the Code Works

The C++, Python, and Java implementations keep two memo tables: one for the survivor value and one for the prefix sum. Every recursive call first handles the tiny base cases, then checks whether the current argument has already been computed, and otherwise evaluates the halved subproblem.

The implementation uses the closed odd and even recurrences above instead of simulating the elimination list. Because each new state only depends on \(\lfloor n/2\rfloor\), the cache remains very small even for \(n=10^{18}\).

All final arithmetic is reduced modulo \(987654321\). The arithmetic logic is written so that subtraction stays non-negative modulo \(M\) and multiplication remains safe in each language's numeric model.

Complexity Analysis

Let \(L(n)\) be the number of distinct arguments reached by repeated halving. Then \(L(n)=O(\log n)\). With memoization, each distinct argument is solved once for the survivor value and once for the prefix sum, and each solve performs only constant-time arithmetic. The total runtime is therefore \(O(\log n)\), and the extra memory usage is also \(O(\log n)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=539
2. Recurrence relation: Wikipedia — Recurrence relation
3. Memoization: Wikipedia — Memoization
4. Divide-and-conquer algorithm: Wikipedia — Divide-and-conquer algorithm
5. Symmetry in mathematics: Wikipedia — Symmetry