Project Euler

Modular Fibonacci Products

The Fibonacci sequence F_1 = 1, F_2 = 1, F_(n+2) = F_(n+1) + F_n. Compute: P(n, m) = prod_(k=1)^n F_k mod m for large n using the Pisano period (periodicity of Fibonacci mod m).

Source sync Apr 19, 2026

Problem #0885

Level Level 14

Solved By 1,177

Languages C++, Python

Answer 827850196

Length 406 words

modular_arithmeticsequencenumber_theory

For a positive integer $d$, let $f(d)$ be the number created by sorting the digits of $d$ in ascending order, removing any zeros. For example, $f(3403) = 334$.

Let $S(n)$ be the sum of $f(d)$ for all positive integers $d$ of $n$ digits or less. You are given $S(1) = 45$ and $S(5) = 1543545675$.

Find $S(18)$. Give you answer modulo $11234556789$.

Problem 885: Modular Fibonacci Products

Mathematical Analysis

Definition (Pisano Period)

The Pisano period $\pi(m)$ is the period of $F_n \bmod m$ . The sequence $F_n \bmod m$ is periodic with period $\pi(m)$ .

Theorem 1 (Existence and Properties)

$\pi(m)$ exists for all $m \geq 2$
$\pi(p) \mid p^2 - 1$ for odd prime $p$ (more precisely, $\pi(p) \mid p - 1$ or $\pi(p) \mid 2(p+1)$ )
$\pi(2) = 3$ , $\pi(5) = 20$
$\pi(10) = 60$ (last digit of Fibonacci repeats every 60)
For $m = p_1^{a_1} \cdots p_k^{a_k}$ : $\pi(m) = \text{lcm}(\pi(p_1^{a_1}), \ldots, \pi(p_k^{a_k}))$

Theorem 2 (Product Periodicity)

Let $Q_r = \prod_{k=1}^{r} F_k \bmod m$ for $r = 1, \ldots, \pi(m)$ . If $\gcd(Q_{\pi(m)}, m) = 1$ , then the sequence $P(n, m) \bmod m$ is eventually periodic.

Specifically, $P(n, m) = Q_{\pi(m)}^{\lfloor n/\pi(m) \rfloor} \cdot Q_{n \bmod \pi(m)} \pmod{m}$ .

Theorem 3 (Fibonacci Product Identity)

\prod_{k=1}^{n} F_k = \frac{F_{n+2}! _F}{F_2! _F}

where $n!_F = \prod_{k=1}^{n} F_k$ is the Fibonacci factorial (fibonorial).

Lemma (Small Pisano Periods)

$m$	$\pi(m)$	$F_k \bmod m$ cycle
2	3	1, 1, 0, 1, 1, 0, …
3	8	1, 1, 2, 0, 2, 2, 1, 0, …
5	20	1, 1, 2, 3, 0, 3, 3, 1, 4, 0, …
7	16
10	60

Concrete Numerical Examples

Fibonacci Products

$n$	$F_n$	$\prod_{k=1}^{n} F_k$	$\bmod 10$
1	1	1	1
2	1	1	1
3	2	2	2
4	3	6	6
5	5	30	0
6	8	240	0
7	13	3120	0
8	21	65520	0

Note: Once $F_5 = 5$ appears, the product mod 10 stays 0.

Pisano Period Computation

$m$	$\pi(m)$
2	3
3	8
4	6
5	20
6	24
7	16
8	12
9	24
10	60
100	300

Matrix Exponentiation for Single Fibonacci Values

The matrix identity $\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n$ allows computing $F_n \bmod m$ in $O(\log n)$ time via repeated squaring.

Proof of Matrix Identity

By induction: base case $n=1$ is immediate. For $n+1$ :

\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}

Important Fibonacci Product Identity

\prod_{k=1}^{n} F_k = F_1 \cdot F_2 \cdots F_n

The first few values: $1, 1, 2, 6, 30, 240, 3120, 65520, 1572480, \ldots$

This sequence is sometimes called the fibonorial and appears in combinatorics (e.g., as a $q$ -analog of $n!$ when $q = \phi$ ).

Divisibility of Fibonacci Products

Since $\gcd(F_m, F_n) = F_{\gcd(m,n)}$ and $p \mid F_{p-1}$ or $p \mid F_{p+1}$ for any odd prime $p$ , the product $\prod F_k$ acquires high powers of each prime factor relatively quickly.

Complexity Analysis

Operation	Time	Space
Compute $\pi(m)$	$O(\pi(m))$	$O(1)$
Compute $P(n, m)$	$O(\pi(m) + \log n)$	$O(\pi(m))$
Matrix method for $F_n \bmod m$	$O(\log n)$	$O(1)$

Answer

\boxed{827850196}

C++ project_euler/problem_885/solution.cpp

/*
 * Problem 885: Modular Fibonacci Products
 * Compute prod_{k=1}^{n} F_k mod m using Pisano period.
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int pisano(int m) {
    int prev = 0, curr = 1;
    for (int i = 1; i <= m * m; i++) {
        int next = (prev + curr) % m;
        prev = curr; curr = next;
        if (prev == 0 && curr == 1) return i;
    }
    return -1;
}

ll fib_product_mod(ll n, int m) {
    int pi = pisano(m);
    vector<ll> Q(pi + 1, 1);
    int a = 0, b = 1;
    for (int k = 1; k <= pi; k++) {
        int next = (a + b) % m;
        a = b; b = next;
        Q[k] = Q[k-1] * a % m;
    }
    ll full = n / pi;
    int rem = n % pi;
    ll result = 1;
    // Q[pi]^full mod m
    ll base = Q[pi]; ll exp = full;
    while (exp > 0) {
        if (exp & 1) result = result * base % m;
        base = base * base % m;
        exp >>= 1;
    }
    result = result * Q[rem] % m;
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cout << "=== Pisano Periods ===" << endl;
    for (int m = 2; m <= 20; m++)
        cout << "pi(" << m << ") = " << pisano(m) << endl;

    cout << "\n=== Products ===" << endl;
    for (int m : {7, 11, 13, 100, 1000}) {
        for (ll n : {10LL, 100LL, 1000LL}) {
            cout << "prod F_k mod " << m << " (n=" << n << ") = "
                 << fib_product_mod(n, m) << endl;
        }
    }

    int MOD = 1e9 + 7;
    cout << "\nAnswer: prod mod 10^9+7 (n=10^6) = " << fib_product_mod(1000000, MOD) << endl;
    return 0;
}

Python project_euler/problem_885/solution.py

"""
Problem 885: Modular Fibonacci Products
Compute prod_{k=1}^{n} F_k mod m using Pisano period.
"""

def fib_mod(n, m):
    """Compute F_n mod m using matrix exponentiation."""
    if n <= 0:
        return 0
    if n <= 2:
        return 1 % m
    def mat_mul(A, B, mod):
        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):
        result = [[1, 0], [0, 1]]
        while p > 0:
            if p & 1:
                result = mat_mul(result, M, mod)
            M = mat_mul(M, M, mod)
            p >>= 1
        return result
    M = [[1, 1], [1, 0]]
    R = mat_pow(M, n - 1, m)
    return R[0][0]

def pisano_period(m):
    """Compute the Pisano period pi(m)."""
    if m <= 1:
        return 1
    prev, curr = 0, 1
    for i in range(1, m * m + 1):
        prev, curr = curr, (prev + curr) % m
        if prev == 0 and curr == 1:
            return i
    return -1

def fibonacci_product_mod(n, m):
    """Compute prod_{k=1}^{n} F_k mod m."""
    result = 1
    a, b = 1, 1  # F_1, F_2
    for k in range(1, n + 1):
        if k == 1:
            fk = 1
        elif k == 2:
            fk = 1
        else:
            a, b = b, (a + b)
            fk = b
        result = (result * (fk % m)) % m
    return result

def fibonacci_product_fast(n, m):
    """Compute prod using Pisano period."""
    pi = pisano_period(m)
    # Compute product over one full period
    Q = [1] * (pi + 1)
    a, b = 0, 1
    for k in range(1, pi + 1):
        a, b = b, (a + b)
        Q[k] = (Q[k-1] * (a % m)) % m
    full_periods = n // pi
    remainder = n % pi
    result = pow(Q[pi], full_periods, m) * Q[remainder] % m
    return result

# --- Verification ---
print("=== Pisano Periods ===")
for m in range(2, 21):
    pi = pisano_period(m)
    print(f"  pi({m}) = {pi}")

print("\n=== Fibonacci Product Verification ===")
for m in [7, 11, 13, 100]:
    for n in [10, 20, 50, 100]:
        slow = fibonacci_product_mod(n, m)
        fast = fibonacci_product_fast(n, m)
        match = "OK" if slow == fast else "FAIL"
        print(f"  prod F_k mod {m} (n={n}): slow={slow}, fast={fast} {match}")
        assert slow == fast

print("\n=== Fibonacci Products (small) ===")
prod = 1
for k in range(1, 12):
    fk = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89][k]
    prod *= fk
    print(f"  prod F_{{1..{k}}} = {prod} (mod 1000: {prod % 1000})")

answer = fibonacci_product_fast(10**6, 10**9 + 7)
print(f"\nAnswer: prod_{{k=1}}^{{10^6}} F_k mod 10^9+7 = {answer}")

# --- 4-Panel Visualization ---