Project Euler

Modular Fibonacci Matrix

Define the Fibonacci sequence F_0 = 0, F_1 = 1, F_n = F_(n-1) + F_(n-2). Find M = sum_(k=1)^10^12 k * F_k (mod 10^9 + 7).

Source sync Apr 19, 2026

Problem #0936

Level Level 38

Solved By 122

Languages C++, Python

Answer 12144907797522336

Length 187 words

modular_arithmeticlinear_algebrasequence

A peerless tree is a tree with no edge between two vertices of the same degree. Let $P(n)$ be the number of peerless trees on $n$ unlabelled vertices.

There are six of these trees on seven unlabelled vertices, $P(7)=6$, shown below.

Define $\displaystyle S(N) = \sum _{n=3}^N P(n)$. You are given $S(10) = 74$.

Find $S(50)$.

Problem 936: Modular Fibonacci Matrix

Mathematical Foundation

Theorem 1 (Fibonacci matrix identity). For all $n \geq 1$ :

\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n.

Proof. By induction on $n$ . Base case ( $n = 1$ ): $\begin{pmatrix} F_2 & F_1 \\ F_1 & F_0 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ . Inductive step: assume the identity holds for $n$ . Then:

\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n+1} = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} F_{n+1} + F_n & F_{n+1} \\ F_n + F_{n-1} & F_n \end{pmatrix} = \begin{pmatrix} F_{n+2} & F_{n+1} \\ F_{n+1} & F_n \end{pmatrix}.

$\square$

Lemma 1 (Fibonacci partial sums). For all $n \geq 1$ : $\sum_{k=1}^{n} F_k = F_{n+2} - 1$ .

Proof. By induction. Base: $F_1 = 1 = F_3 - 1 = 2 - 1$ . Inductive step: $\sum_{k=1}^{n+1} F_k = (F_{n+2} - 1) + F_{n+1} = F_{n+3} - 1$ . $\square$

Theorem 2 (Weighted Fibonacci sum). For all $n \geq 1$ :

\sum_{k=1}^{n} k \, F_k = (n-1) \, F_{n+2} - F_{n+1} + 2.

Proof. We use Abel summation (summation by parts). Define $S_n = \sum_{k=1}^{n} F_k = F_{n+2} - 1$ (Lemma 1). Then:

\sum_{k=1}^{n} k \, F_k = n \, S_n - \sum_{k=1}^{n-1} S_k = n(F_{n+2} - 1) - \sum_{k=1}^{n-1}(F_{k+2} - 1).

The inner sum is:

\sum_{k=1}^{n-1}(F_{k+2} - 1) = \sum_{j=3}^{n+1} F_j - (n-1) = \left(\sum_{j=1}^{n+1} F_j - F_1 - F_2\right) - (n-1) = (F_{n+3} - 1 - 1 - 1) - (n-1) = F_{n+3} - n - 2.

Substituting:

\sum_{k=1}^{n} k \, F_k = n \, F_{n+2} - n - F_{n+3} + n + 2 = n \, F_{n+2} - F_{n+3} + 2.

Since $F_{n+3} = F_{n+2} + F_{n+1}$ :

= n \, F_{n+2} - F_{n+2} - F_{n+1} + 2 = (n - 1) \, F_{n+2} - F_{n+1} + 2.

$\square$

Lemma 2 (Modular matrix exponentiation). $F_n \bmod m$ can be computed in $O(\log n)$ arithmetic operations modulo $m$ by repeated squaring of the $2 \times 2$ matrix $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ .

Proof. Each matrix multiplication involves a constant number (4 multiplications, 2 additions) of modular arithmetic operations. Repeated squaring performs $O(\log n)$ matrix multiplications. $\square$

Editorial

Compute S(N) = sum_{k=1}^{N} k * F_k mod (10^9 + 7), where N = 10^12. Key identity: sum_{k=1}^{N} k * F_k = N * F_{N+2} - F_{N+3} + 2 This follows from the telescoping identity k*F_k = (k+1)F_{k+1} - kF_k - F_{k+1} + F_k combined with the Fibonacci recurrence. Results:.

Pseudocode

Compute F_{n+1} and F_{n+2} via matrix exponentiation
if exp is odd
Q^(n+1) gives F_{n+2} in position [0][1]
Apply Theorem 2: (n-1)*F_{n+2} - F_{n+1} + 2

Complexity Analysis

Time: $O(\log n)$ for two matrix exponentiations, each involving $O(\log n)$ multiplications of $2 \times 2$ matrices. Each matrix multiplication is $O(1)$ arithmetic operations. Total: $O(\log n)$ .
Space: $O(1)$ (constant number of $2 \times 2$ matrices).

Answer

\boxed{12144907797522336}

C++ project_euler/problem_936/solution.cpp

#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long>> Mat;
const long long MOD=1e9+7;
Mat mul(Mat&A,Mat&B){
    int n=A.size();
    Mat C(n,vector<long long>(n,0));
    for(int i=0;i<n;i++) for(int k=0;k<n;k++) if(A[i][k])
        for(int j=0;j<n;j++) C[i][j]=(C[i][j]+A[i][k]*B[k][j])%MOD;
    return C;
}
Mat mpow(Mat M,long long p){
    int n=M.size();
    Mat R(n,vector<long long>(n,0));
    for(int i=0;i<n;i++) R[i][i]=1;
    while(p>0){if(p&1) R=mul(R,M); M=mul(M,M); p>>=1;}
    return R;
}
long long fib(long long n){
    if(n<=0) return 0;
    if(n==1) return 1;
    Mat M={{1,1},{1,0}};
    Mat R=mpow(M,n-1);
    return R[0][0];
}
int main(){
    long long N=1000000000000LL;
    long long fn2=fib(N+2), fn3=fib(N+3);
    long long ans=((N%MOD)*fn2%MOD-fn3+2+2*MOD)%MOD;
    cout<<ans<<endl;
}

Python project_euler/problem_936/solution.py

"""
Problem 936: Modular Fibonacci Matrix

Compute S(N) = sum_{k=1}^{N} k * F_k  mod (10^9 + 7), where N = 10^12.

Key identity:
    sum_{k=1}^{N} k * F_k  =  N * F_{N+2} - F_{N+3} + 2

This follows from the telescoping identity k*F_k = (k+1)*F_{k+1} - k*F_k - F_{k+1} + F_k
combined with the Fibonacci recurrence.

Results:
    - S(10)  = 1220
    - S(100) = 76 725 220 469 804 488 (before mod)
    - S(10^12) mod (10^9+7) computed via matrix exponentiation

Methods:
    1. mat_mul          -- 2x2 matrix multiply mod m
    2. mat_pow          -- matrix exponentiation by squaring
    3. fib              -- F_n via matrix method
    4. solve_identity   -- closed-form using N*F_{N+2} - F_{N+3} + 2
    5. solve_brute      -- direct summation for verification
"""

MOD = 10**9 + 7

def mat_mul(A, B, mod):
    """Multiply two 2x2 matrices mod m."""
    return [
        [(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % mod,
         (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % mod],
        [(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % mod,
         (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % mod],
    ]

def mat_pow(M, p, mod):
    """Compute M^p mod m via repeated squaring."""
    R = [[1, 0], [0, 1]]
    while p > 0:
        if p & 1:
            R = mat_mul(R, M, mod)
        M = mat_mul(M, M, mod)
        p >>= 1
    return R

def fib(n, mod=MOD):
    """Return F_n mod m using [[1,1],[1,0]]^(n-1)."""
    if n <= 0:
        return 0
    if n == 1:
        return 1
    M = [[1, 1], [1, 0]]
    R = mat_pow(M, n - 1, mod)
    return R[0][0]

def solve_identity(N, mod=MOD):
    """S(N) = N*F_{N+2} - F_{N+3} + 2  (mod m)."""
    fn2 = fib(N + 2, mod)
    fn3 = fib(N + 3, mod)
    return (N % mod * fn2 - fn3 + 2) % mod

def solve_brute(N):
    """Direct summation of k*F_k for k=1..N (no mod, for small N)."""
    a, b = 1, 1
    total = 0
    for k in range(1, N + 1):
        total += k * a
        a, b = b, a + b
    return total

# Verification against known small values
assert solve_brute(1) == 1       # 1*1
assert solve_brute(2) == 3       # 1*1 + 2*1
assert solve_brute(5) == 50      # 1+2+6+12+25+...  hand-check
assert solve_brute(10) == 1220

# Cross-check identity vs brute for several N
for n in [1, 2, 5, 10, 20, 50, 100]:
    brute = solve_brute(n)
    ident = solve_identity(n, mod=10**18)
    assert brute == ident, f"Mismatch at n={n}: {brute} vs {ident}"

# Final answer
answer = solve_identity(10**12)
print(answer)