Detailed mathematical approach

Problem Summary

For each \(n\in\{1,\dots,30\}\), let \(a_n\) be the largest real root of

$x^3-2^n x^2+n=0.$

The task is to compute

$\sum_{n=1}^{30}\left\lfloor a_n^{987654321}\right\rfloor \pmod{10^8}.$

A direct floating-point evaluation of such enormous powers would be fragile and unnecessary. The local C++, Python, and Java solutions instead turn the problem into an exact linear recurrence modulo \(10^8\).

Mathematical Approach

Step 1: Locate the Three Real Roots

Write \(c=2^n\) and \(f(x)=x^3-cx^2+n\). The implementations rely on the fact that the cubic has three real roots, with one large positive root and two small roots near the origin.

Indeed,

$f(-1)=n-1-c<0,\qquad f(0)=n>0,$

so there is a root \(\gamma\in(-1,0)\). Also,

$f(1)=n+1-c\le 0,\qquad f(0)=n>0,$

so there is a root \(\beta\in(0,1]\), with \(\beta=1\) only when \(n=1\). Finally,

$f(c)=n>0,\qquad f(c-1)=n-(c-1)^2\le 0,$

so the largest root \(\alpha=a_n\) lies in \((c-1,c)\). Thus the three roots satisfy

$\gamma\in(-1,0),\qquad \beta\in(0,1],\qquad \alpha\in(2^n-1,2^n).$

By Vieta's formulas,

$\alpha+\beta+\gamma=c,\qquad \alpha\beta+\alpha\gamma+\beta\gamma=0,\qquad \alpha\beta\gamma=-n.$

Step 2: Define the Power Sums

Let

$S_k=\alpha^k+\beta^k+\gamma^k.$

Because every root \(r\in\{\alpha,\beta,\gamma\}\) satisfies

$r^3=cr^2-n,$

multiplying by \(r^{k-3}\) gives

$r^k=cr^{k-1}-nr^{k-3}\qquad (k\ge 3).$

Summing over the three roots yields the recurrence used in every implementation:

$\boxed{S_k=cS_{k-1}-nS_{k-3}\qquad (k\ge 3).}$

The initial values are immediate:

$S_0=3,$

$S_1=\alpha+\beta+\gamma=c,$

$S_2=(\alpha+\beta+\gamma)^2-2(\alpha\beta+\alpha\gamma+\beta\gamma)=c^2.$

So the entire problem is reduced to a third-order linear recurrence.

Step 3: Why \(\left\lfloor a_n^m\right\rfloor=S_m-1\) for Odd \(m\)

Let \(m\) be odd and define the small-root contribution

$\rho_m=\beta^m+\gamma^m.$

Since \(\gamma<0\) and \(m\) is odd, we have \(\gamma^m<0\). We also know

$\beta+\gamma=c-\alpha,$

and because \(\alpha\in(c-1,c)\), this implies

$0<\beta+\gamma<1.$

In particular, \(\beta>|\gamma|\). For odd \(m\), monotonicity of \(x\mapsto x^m\) on positive numbers gives

$\beta^m>|\gamma|^m,$

hence

$0<\rho_m=\beta^m-|\gamma|^m.$

At the same time, \(\beta\le 1\) and \(|\gamma|<1\), so

$\rho_m<1.$

Therefore

$0<\rho_m<1,$

and since \(\alpha^m=S_m-\rho_m\), we obtain the crucial identity

$\boxed{\left\lfloor \alpha^m\right\rfloor=\left\lfloor S_m-\rho_m\right\rfloor=S_m-1.}$

This is exactly why the production code never needs to approximate \(a_n^{987654321}\) directly.

Step 4: Convert the Recurrence to Matrix Exponentiation

The recurrence has fixed order 3, so the state vector

$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix}$

evolves by

$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix} = \begin{bmatrix} c & 0 & -n\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix}S_{k-1}\\S_{k-2}\\S_{k-3}\end{bmatrix}.$

Hence, for \(m\ge 2\),

$\begin{bmatrix}S_m\\S_{m-1}\\S_{m-2}\end{bmatrix} = M^{m-2} \begin{bmatrix}S_2\\S_1\\S_0\end{bmatrix}.$

The solutions compute this power by binary exponentiation, reducing every multiplication modulo \(10^8\). In modular arithmetic the entry \(-n\) is stored as

$10^8-(n\bmod 10^8),$

which is why the source code writes the transition matrix with a non-negative last coefficient.

Step 5: A Small Checkpoint

Take \(n=2\), so \(c=4\). Then

$S_0=3,\qquad S_1=4,\qquad S_2=16.$

For the odd exponent \(m=3\), the recurrence gives

$S_3=4\cdot 16-2\cdot 3=58.$

Since \(0<\beta^3+\gamma^3<1\), we conclude

$\left\lfloor a_2^3\right\rfloor=S_3-1=57.$

The C++ implementation performs this kind of spot check numerically for small odd exponents before relying on the modular fast path for the full input.

How the Code Works

The three language versions all implement the same pipeline. First, powMod computes \(c=2^n\bmod 10^8\). Then multiplyMatrix and powerMatrix raise the \(3\times 3\) transition matrix to the power \(m-2\). The function computeNewtonSumMod returns \(S_m\bmod 10^8\), handling the base cases \(m=0,1,2\) directly and using matrix exponentiation otherwise.

After that, computeTermMod applies the identity \(\lfloor a_n^m\rfloor\equiv S_m-1\pmod{10^8}\), and solve sums the terms for \(n=1\) through \(30\). The longer C++ file also contains validation helpers: it checks the statement sample \(\lfloor a_2^2\rfloor=14\), verifies the matrix recurrence against a direct iterative recurrence, compares the floor identity against floating-point root calculations on small cases, and tests thread consistency. Those checks justify the method, but the final answer path itself is entirely integer-based.

Complexity Analysis

For one fixed \(n\), the dominant cost is exponentiating a \(3\times 3\) matrix to power \(m-2\), which takes \(O(\log m)\) matrix multiplications. The problem has only 30 values of \(n\), so the total running time is

$O(30\log m)=O(\log m),$

with \(O(1)\) auxiliary memory. The C++ version can parallelize the 30 independent \(n\)-values, but that changes only wall-clock time, not asymptotic complexity.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=356
2. Vieta's formulas: Wikipedia - Vieta's formulas
3. Newton sums / power sums: Wikipedia - Newton's identities
4. Matrix exponentiation for linear recurrences: cp-algorithms - binary exponentiation of recurrence transitions