Project Euler Problem 435

Solution

Answer: 252541322550

Let

$$F_n(x)=\sum_{i=0}^n f_i x^i,$$

where $f_0=0,\ f_1=1,\ f_n=f_{n-1}+f_{n-2}$, and we want

$$\sum_{x=0}^{100} F_n(x) \quad \text{for } n=10^{15}$$

modulo

$$15! = 1{,}307{,}674{,}368{,}000.$$

The key observation is that for fixed $x$, $F_n(x)$ satisfies a linear recurrence, so we can compute it in $O(\log n)$ time using matrix exponentiation.

For each $x$, define:

$$g_k=f_k x^k,\qquad h_k=f_{k+1}x^k.$$

Then:

$$g_{k+1}=x h_k,$$

$$h_{k+1}=x(g_k+h_k),$$

and

$$F_{k+1}=F_k+g_{k+1}.$$

This gives the matrix recurrence

$$\begin{bmatrix} g_{k+1}\ h_{k+1}\ F_{k+1} \end{bmatrix} = \begin{bmatrix} 0 & x & 0\ x & x & 0\ 0 & x & 1 \end{bmatrix} \begin{bmatrix} g_k\ h_k\ F_k \end{bmatrix},$$

with initial state

$$(g_0,h_0,F_0)=(0,1,0).$$

Thus, for each $x\in[0,100]$, compute $M_x^n$ modulo $15!$, extract $F_n(x)$, and sum all results modulo $15!$.

Python implementation:

MOD = 1307674368000  # 15!
N = 10**15

def mat_mul(A, B, mod):
    """Multiply two 3x3 matrices modulo mod."""
    return [
        [
            sum(A[i][k] * B[k][j] for k in range(3)) % mod
            for j in range(3)
        ]
        for i in range(3)
    ]

def F_mod(n, x, mod):
    """Compute F_n(x) modulo mod using matrix exponentiation."""
    M = [
        [0, x % mod, 0],
        [x % mod, x % mod, 0],
        [0, x % mod, 1]
    ]

    # State vector: [g_0, h_0, F_0] = [0,1,0]
    vec = [0, 1, 0]

    while n:
        if n & 1:
            vec = [
                sum(M[i][j] * vec[j] for j in range(3)) % mod
                for i in range(3)
            ]
        M = mat_mul(M, M, mod)
        n >>= 1

    return vec[2]

answer = 0
for x in range(101):
    answer = (answer + F_mod(N, x, MOD)) % MOD

print(answer)

Sanity check against the example:

$F_7(11)=268357683$

The code reproduces this exactly, confirming the recurrence and matrix setup are correct.

Running the computation for $n=10^{15}$ gives:

Answer: 252541322550