Detailed mathematical approach

Problem Summary

The sequence is defined by

$s_0=0,\qquad s_{k+1}=\left(s_k^2+45\right)\bmod\left(10^9+7\right).$

From the first \(n\) terms \(S_n=(s_0,s_1,\dots,s_{n-1})\), two players alternately take either the leftmost or the rightmost remaining term. Both players are optimal and want to maximize their own final total. Let \(G(n)\) denote the first player's total. The implementations verify the checkpoints

$G(2)=45,\qquad G(4)=4284990,\qquad G(100)=26365463243,\qquad G(10000)=2495838522951.$

A direct dynamic program on all intervals would be far too expensive for large \(n\), so the solution compresses the game mathematically before using the eventual periodicity of the recurrence.

Mathematical Approach

The solution has three layers. First, rewrite the game in terms of score difference instead of absolute totals. Second, compress local peaks, which turns the sequence into a much simpler reduced form. Third, use the fact that the modular recurrence eventually becomes periodic, so large \(n\) can be handled by evaluating only a small calibration prefix and one full aligned cycle block.

Step 1: Rewrite the Game as a Difference Problem

For any finite sequence \(X=(x_1,\dots,x_m)\), let \(D(X)\) be the optimal score difference

$D(X)=\text{(first player's total)}-\text{(second player's total)}.$

If the current player chooses the left end, the opponent then faces \((x_2,\dots,x_m)\); if the current player chooses the right end, the opponent then faces \((x_1,\dots,x_{m-1})\). Therefore

$D(x_1,\dots,x_m)=\max\left(x_1-D(x_2,\dots,x_m),\ x_m-D(x_1,\dots,x_{m-1})\right),$

with \(D(\varnothing)=0\).

If \(\Sigma(X)=x_1+\cdots+x_m\), then the first player's score on \(X\) is

$F(X)=\frac{\Sigma(X)+D(X)}{2}.$

So for \(S_n\) it is enough to compute the ordinary sum and the optimal difference \(D(S_n)\).

Step 2: Eliminate a Local Peak

Consider three consecutive values \((a,b,c)\) with \(b\ge a\) and \(b\ge c\). For a two-term game we have

$D(a,b)=b-a,\qquad D(b,c)=b-c.$

Substituting those into the recurrence for three terms gives

$D(a,b,c)=\max\left(a-(b-c),\ c-(b-a)\right)=a-b+c.$

So whenever the middle term is a local maximum, the triple behaves, from the viewpoint of score difference, exactly like the single value \(a-b+c\). The implementations scan from left to right, keep a reduced stack, and repeatedly apply this identity to the rightmost triple until no such peak remains.

This is the key compression step: many terms disappear, but the optimal difference of the processed prefix stays unchanged.

Step 3: The Reduced Sequence Has No Interior Local Maximum

After all possible reductions, every interior term is strictly smaller than at least one neighbor. That means the reduced sequence has no local maxima. Such a sequence must be monotone or have a single valley: it can go down and later go up, but it cannot go up and then down without creating a removable peak.

For a valley-shaped sequence, the larger of the two exposed ends is always an optimal move. Once that larger end is removed, the remaining sequence is still valley-shaped, so the same reasoning applies again.

Therefore, if the reduced sequence is \(w_1,\dots,w_t\), then the optimal difference is obtained by the greedy alternating sum produced by repeatedly taking the larger end:

$D(S_n)=w_{i_1}-w_{i_2}+w_{i_3}-w_{i_4}+\cdots.$

Combining this with the original unreduced total sum yields \(G(n)\).

Step 4: The Recurrence Is Eventually Periodic

The update rule uses arithmetic modulo \(10^9+7\), so every term lies in a finite set. Because the next value depends only on the current value, the sequence must eventually repeat a state and then continue periodically forever.

Write \(p\) for the length of the nonrepeating prefix and \(c\) for the cycle length. Then

$s_{k+c}=s_k\qquad\text{for all }k\ge p.$

If \(n\) is not very large, evaluating the explicit prefix is sufficient. For huge \(n\), however, we must exploit the periodic tail without constructing all \(n\) terms.

Step 5: One Aligned Full Cycle Adds a Constant Increment

Assume \(n>p\), and let

$r=(n-p)\bmod c.$

Take the anchor prefix consisting of the first \(p+r\) terms. This stops at a fixed phase inside the cycle. Now append the next full cycle starting from exactly that same phase. That extra block has length \(c\), ends at the same phase where it started, and therefore puts the reduced game state back into the same structural position.

Let \(A_r\) be the first-player score of the anchor prefix, and let \(B_r\) be the first-player score after appending one such full aligned cycle block. Because every additional aligned full cycle starts and ends at the same phase, each one contributes the same increment \(B_r-A_r\). If

$k=\frac{n-(p+r)}{c},$

then the score is affine in the number of full blocks:

$G(n)=A_r+k(B_r-A_r).$

This is the acceleration that makes \(n=10^8\) feasible.

Worked Example: \(n=4\)

The first four terms are

$0,\ 45,\ 2070,\ 4284945.$

They are strictly increasing, so no local-peak reduction occurs. On such a sequence, the larger exposed end is always taken first, so the alternating difference is

$D(S_4)=4284945-2070+45-0=4282920.$

The total sum is

$\Sigma(S_4)=0+45+2070+4284945=4287060.$

Hence

$G(4)=\frac{4287060+4282920}{2}=4284990,$

which matches the checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations first generate sequence values until the first repeated state appears. A hash table maps each encountered value to its first position, which immediately yields the preperiod length and the cycle length.

To evaluate a concrete finite prefix, the implementation performs one pass over the terms. During that pass it accumulates the ordinary sum and simultaneously maintains the reduced stack obtained by repeatedly collapsing rightmost local peaks. After the scan, a two-pointer pass over the ends of the reduced structure computes the greedy alternating difference.

For large \(n\), the implementation evaluates only two calibration inputs: the anchor prefix and the anchor prefix followed by one aligned full cycle block. Their difference is the fixed gain per additional full cycle, so the final result is recovered by one multiplication and one addition rather than by simulating the whole sequence.

Complexity Analysis

Let \(L=p+c\) be the number of generated terms needed to detect the first repeat. Cycle detection costs \(O(L)\) time and \(O(L)\) memory. Evaluating a concrete prefix of length at most \(p+2c\) is also linear, because each term is pushed once and can be removed by the reduction at most once. Thus the full method runs in \(O(p+c)\) time and uses \(O(p+c)\) memory, instead of \(O(n)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=477
2. Cycle detection: Wikipedia - Cycle detection
3. Minimax principle: Wikipedia - Minimax
4. Periodic sequence: Wikipedia - Periodic function