Project Euler Problem 356

Solution

Answer: 28010159

Let the roots of

$$g_n(x)=x^3-2^n x^2+n$$

be $a_n,b_n,c_n$, where $a_n$ is the largest real root.

We seek

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

modulo $10^8$.

1. Mathematical analysis

Step 1: Relating the floor to a power sum

By Viète’s formulas,

$$a_n+b_n+c_n = 2^n,$$

$$a_nb_n+a_nc_n+b_nc_n=0,$$

$$a_nb_nc_n=-n.$$

For $n\ge 2$, the polynomial has one large positive root $a_n$, one small positive root $b_n\in(0,1)$, and one negative root $c_n\in(-1,0)$. For $n=1$, the roots are

$$\phi,\quad 1,\quad -\frac1\phi.$$

Thus in every case:

$$0<b_n\le 1,\qquad -1<c_n<0,$$

and since the exponent

$$m=987654321$$

is odd,

$$0<b_n^m+c_n^m<1.$$

Define the integer power sum

$$S_k = a_n^k+b_n^k+c_n^k.$$

Then

$$a_n^m=S_m-(b_n^m+c_n^m),$$

with $0<b_n^m+c_n^m<1$. Therefore:

$$\boxed{\lfloor a_n^m\rfloor = S_m-1.}$$

So we only need $S_m$.

Step 2: Deriving a recurrence for $S_k$

Every root $r$ satisfies

$$r^3=2^n r^2-n.$$

Multiplying by $r^{k-3}$,

$$r^k = 2^n r^{k-1} - n r^{k-3}.$$

Summing over all three roots:

$$\boxed{ S_k = 2^n S_{k-1} - n S_{k-3} } \qquad (k\ge 3).$$

Initial values:

$$S_0=3,$$

$$S_1=a_n+b_n+c_n=2^n,$$

$$S_2=(a_n+b_n+c_n)^2 -2(a_nb_n+a_nc_n+b_nc_n) =2^{2n}.$$

Hence:

$$S_0=3,\qquad S_1=2^n,\qquad S_2=2^{2n}.$$

Since we only need the last eight digits, we compute the recurrence modulo

$$10^8.$$

Use matrix exponentiation:

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

Exponentiating this $3\times3$ matrix to power $m-2$ gives $S_m$ in $O(\log m)$.

2. Python implementation

MOD = 10**8
M = 987654321

def mat_mul(A, B):
    """Multiply two 3x3 matrices modulo MOD."""
    return [
        [
            (
                A[i][0] * B[0][j]
                + A[i][1] * B[1][j]
                + A[i][2] * B[2][j]
            ) % MOD
            for j in range(3)
        ]
        for i in range(3)
    ]

def mat_pow(A, exponent):
    """Fast matrix exponentiation."""
    result = [
        [1, 0, 0],
        [0, 1, 0],
        [0, 0, 1]
    ]

    while exponent:
        if exponent & 1:
            result = mat_mul(result, A)

        A = mat_mul(A, A)
        exponent >>= 1

    return result

answer = 0

for n in range(1, 31):

    two_n = pow(2, n, MOD)

    # Transition matrix for:
    # S_k = 2^n * S_{k-1} - n * S_{k-3}
    transition = [
        [two_n, 0, (-n) % MOD],
        [1, 0, 0],
        [0, 1, 0]
    ]

    # Initial vector [S_2, S_1, S_0]
    initial = [
        pow(2, 2 * n, MOD),
        two_n,
        3
    ]

    # Compute S_M
    power_matrix = mat_pow(transition, M - 2)

    S_M = (
        power_matrix[0][0] * initial[0]
        + power_matrix[0][1] * initial[1]
        + power_matrix[0][2] * initial[2]
    ) % MOD

    # floor(a_n^M) = S_M - 1
    answer = (answer + S_M - 1) % MOD

print(answer)

3. Code walkthrough

mat_mul multiplies two $3\times3$ matrices modulo $10^8$.
mat_pow computes matrix powers using binary exponentiation in $O(\log M)$.
For each $n=1,\dots,30$:
Build the recurrence matrix

$$\begin{pmatrix} 2^n & 0 & -n\ 1&0&0\ 0&1&0 \end{pmatrix}.$$

Use initial values:

$$(S_2,S_1,S_0)=(2^{2n},2^n,3).$$

Compute $S_M$.
Add $S_M-1$, because

$$\lfloor a_n^M\rfloor=S_M-1.$$

Small example check

For $n=2$:

$$a_2 = 3.86619826\ldots$$

The recurrence gives integer values $S_k$, and indeed

$$\lfloor a_2^{11}\rfloor = S_{11}-1,$$

matching direct numerical computation.

4. Final verification

We only need the last 8 digits, so modulo $10^8$ arithmetic is valid.
The correction term is always exactly $-1$ because the other two roots contribute a number strictly between $0$ and $1$.
Matrix exponentiation makes the enormous exponent $987654321$ computationally trivial.

Answer: 28010159