Detailed mathematical approach

Problem Summary

Let the Fibonacci numbers be \(f_0=0\), \(f_1=1\), and \(f_n=f_{n-1}+f_{n-2}\). For each integer \(x\), define the truncated polynomial

$$F_n(x)=\sum_{k=0}^{n} f_k x^k.$$

The task is to evaluate

$$\sum_{x=0}^{100} F_n(x) \pmod{15!}$$

for the enormous index \(n=10^{15}\). A direct loop over all Fibonacci terms is impossible, so the key is to turn the polynomial sum into a fixed-size linear recurrence that can be exponentiated in logarithmic time.

Mathematical Approach

Step 1: Isolate the weighted Fibonacci term

For a fixed value of \(x\), define

$$a_k=f_k x^k.$$

Using the Fibonacci recurrence,

$$a_{k+1}=f_{k+1}x^{k+1}=(f_k+f_{k-1})x^{k+1}=x a_k + x^2 a_{k-1}.$$

So once \(x\) is fixed, the sequence \(a_k\) satisfies a second-order linear recurrence with constant coefficients \(x\) and \(x^2\).

Step 2: Add the partial sum to the state vector

The polynomial value itself is the prefix sum of the \(a_k\):

$$F_k(x)=\sum_{i=0}^{k} a_i.$$

Therefore

$$F_{k+1}(x)=F_k(x)+a_{k+1}.$$

Now combine the recurrence for \(a_k\) with the update for the running sum. With the state vector

$$v_k=\begin{bmatrix}a_k\\ a_{k-1}\\ F_k(x)\end{bmatrix},$$

we obtain the linear transition

$$v_{k+1}=T_x v_k,\qquad T_x=\begin{bmatrix} x & x^2 & 0\\ 1 & 0 & 0\\ x & x^2 & 1 \end{bmatrix}.$$

The first row reproduces \(a_{k+1}=x a_k+x^2 a_{k-1}\), the second row shifts \(a_k\) into the next position, and the third row accumulates the new term into the polynomial sum.

Step 3: Base state and matrix power

For \(k=1\),

$$a_1=f_1 x=x,\qquad a_0=f_0=0,\qquad F_1(x)=f_0+f_1 x=x.$$

Hence the base vector is

$$v_1=\begin{bmatrix}x\\ 0\\ x\end{bmatrix}.$$

For every \(n\ge 1\),

$$v_n=T_x^{\,n-1}v_1,$$

and the desired value \(F_n(x)\) is the third component of \(v_n\). The special case \(n=0\) is immediate because \(F_0(x)=f_0=0\).

Step 4: Why repeated squaring is the right tool

The matrix \(T_x\) has fixed size \(3\times 3\), so its \((n-1)\)-st power can be computed by binary exponentiation in \(O(\log n)\) matrix multiplications. Every operation is performed modulo

$$M=15!=1307674368000.$$

This keeps the numbers bounded while matching the modulus required by the problem.

Alternative closed form and why the implementation avoids division

The truncated generating function also satisfies

$$\left(1-x-x^2\right)F_n(x)=x-f_{n+1}x^{n+1}-f_n x^{n+2}.$$

Over the integers this identity is correct and useful, but modulo \(15!\) the factor \(1-x-x^2\) is not always invertible. For example, at \(x=2\) it equals \(-5\), and \(5\) shares a factor with \(15!\). The matrix formulation is therefore preferable: it is division-free and works uniformly for every \(x\in\{0,\dots,100\}\).

Worked checks

Several small cases confirm the recurrence.

First, \(F_n(0)=0\) for all \(n\), because every term contains either \(f_0=0\) or a positive power of \(0\).

Second, for \(n=7\) and \(x=11\),

$$F_7(11)=11+11^2+2\cdot 11^3+3\cdot 11^4+5\cdot 11^5+8\cdot 11^6+13\cdot 11^7=268357683.$$

This matches the value produced by the matrix method.

A larger checkpoint is

$$\sum_{x=0}^{10} F_{20}(x)\equiv 1044074802100 \pmod{15!},$$

which is exactly the validation target used by the implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. For each \(x\in\{0,\dots,100\}\), they build the transition matrix \(T_x\), raise it to the power \(n-1\) by repeated squaring, multiply by the base vector, and read the third component as \(F_n(x)\). These 101 values are then accumulated modulo \(15!\).

Because \(15!\approx 1.3\times 10^{12}\), an unreduced product of two residues can exceed ordinary 64-bit multiplication in some languages. The implementations therefore perform modular multiplication carefully before each reduction, but the mathematical algorithm itself remains the same in all three languages.

Complexity Analysis

A \(3\times 3\) matrix multiplication has constant cost, and binary exponentiation uses \(O(\log n)\) such multiplications. Therefore each single value \(F_n(x)\) is computed in \(O(\log n)\) time and \(O(1)\) extra space. Since the outer sum runs over exactly 101 values of \(x\), the full computation is still \(O(101\log n)=O(\log n)\) with a very small constant factor, and the memory usage stays \(O(1)\).

References

1. Problem page: https://projecteuler.net/problem=435
2. Fibonacci numbers: Wikipedia — Fibonacci number
3. Matrix exponentiation / exponentiation by squaring: Wikipedia — Exponentiation by squaring
4. Generating functions for Fibonacci numbers: Wikipedia — Fibonacci number, generating function section