Project Euler

Pisano Period Computation

The Pisano period pi(m) is the period of the Fibonacci sequence modulo m. Find sum_(m=2)^1000 pi(m).

Source sync Apr 19, 2026

Problem #0967

Level Level 35

Solved By 218

Languages C++, Python

Answer 357591131712034236

Length 228 words

modular_arithmeticsequencenumber_theory

A positive integer is considered -trivisible if the sum of all different prime factors of which are not larger than is divisible by .

For example, is -trivisible because which is divisible by . Similarly, is -trivisible because all primes dividing are larger than , and the empty summation is divisible by .
On the other hand, is not -trivisible because the sum of relevant primes is which is not divisible by .

Let be the number of -trivisible integers not larger than .

For example, , the -trivisible numbers being .
You are also given and .

Find .

Problem 967: Pisano Period Computation

Mathematical Analysis

Pisano Period Existence

Theorem. For every $m \ge 1$ , the Fibonacci sequence modulo $m$ is periodic. The period $\pi(m)$ satisfies $\pi(m) \le 6m$ .

Proof. The pairs $(F_k \bmod m, F_{k+1} \bmod m)$ can take at most $m^2$ values. By the pigeonhole principle, some pair repeats. Since the Fibonacci recurrence is invertible modulo $m$ (given $(F_k, F_{k+1})$ , we can recover $F_{k-1} = F_{k+1} - F_k$ ), the sequence is purely periodic. Wall (1960) proved the sharper bound $\pi(m) \le 6m$ . $\square$

Properties of Pisano Periods

Theorem (Multiplicativity). For $\gcd(a, b) = 1$ : $\pi(ab) = \operatorname{lcm}(\pi(a), \pi(b))$ .

Theorem (Prime Pisano Periods). For prime $p$ :

If $p = 5$ : $\pi(5) = 20$ .
If $p \equiv \pm 1 \pmod{5}$ : $\pi(p) \mid p - 1$ .
If $p \equiv \pm 2 \pmod{5}$ : $\pi(p) \mid 2(p + 1)$ .

Concrete Values

$m$	$\pi(m)$	$F$ mod $m$ sequence
2	3	0,1,1,0,1,1,…
3	8	0,1,1,2,0,2,2,1,0,…
4	6	0,1,1,2,3,1,0,…
5	20
10	60

Derivation

Editorial

Sum of pi(m) for m = 2..1000, where pi(m) is the Pisano period — the period of Fibonacci numbers modulo m. The Pisano period pi(m) is the smallest positive integer k such that F(k) = 0 (mod m) and F(k+1) = 1 (mod m). Known properties:. We iterate until returning to $(0, 1)$ . Finally, the number of steps is $\pi(m)$ .

Pseudocode

Compute $(F_k, F_{k+1}) \bmod m$ starting from $(0, 1)$
Iterate until returning to $(0, 1)$
The number of steps is $\pi(m)$

Proof of Correctness

The period is detected when the pair $(F_k, F_{k+1}) \equiv (0, 1) \pmod{m}$ for the first time with $k > 0$ . Since the recurrence is deterministic and the state space is finite, this always occurs.

Complexity Analysis

$O(\sum_{m=2}^{N} \pi(m))$ total work. Since $\pi(m) \le 6m$ , total is $O(N^2)$ .

Answer

\boxed{357591131712034236}

C++ project_euler/problem_967/solution.cpp

#include <bits/stdc++.h>
using namespace std;
int pisano(int m) {
    if (m == 1) return 1;
    int a = 0, b = 1;
    for (int k = 1; k <= 6*m+1; k++) {
        int c = (a+b)%m; a = b; b = c;
        if (a == 0 && b == 1) return k;
    }
    return -1;
}
int main() {
    long long total = 0;
    for (int m = 2; m <= 1000; m++) total += pisano(m);
    cout << total << endl;
    return 0;
}

Python project_euler/problem_967/solution.py

"""
Problem 967: Pisano Period Computation

Sum of pi(m) for m = 2..1000, where pi(m) is the Pisano period — the period
of Fibonacci numbers modulo m.

The Pisano period pi(m) is the smallest positive integer k such that
F(k) = 0 (mod m) and F(k+1) = 1 (mod m). Known properties:
    - pi(1) = 1
    - pi(2) = 3
    - pi(10) = 60
    - pi(p) divides p-1 if p = +/-1 (mod 5), divides 2(p+1) otherwise
    - pi(m) <= 6m, with equality never achieved

Key results:
    - Sum of pi(m) for m=2..1000
    - pi(m) has multiplicative-like structure for coprime factors

Methods:
    1. pisano_period           — direct computation via Fibonacci iteration
    2. pisano_period_prime     — optimized for prime moduli
    3. verify_pisano_properties — check known theoretical properties
    4. cumulative_sum_analysis — growth of sum over range
"""

def pisano_period(m):
    """Compute Pisano period pi(m) by finding period of Fib mod m."""
    if m == 1:
        return 1
    a, b = 0, 1
    for k in range(1, 6 * m + 2):
        a, b = b, (a + b) % m
        if a == 0 and b == 1:
            return k
    return -1

def fibonacci_mod_sequence(m, length):
    """Generate first 'length' Fibonacci numbers mod m."""
    seq = [0, 1]
    for _ in range(length - 2):
        seq.append((seq[-1] + seq[-2]) % m)
    return seq

def verify_known_pisano():
    """Check known Pisano period values."""
    known = {
        1: 1, 2: 3, 3: 8, 4: 6, 5: 20,
        6: 24, 7: 16, 8: 12, 9: 24, 10: 60
    }
    for m, expected in known.items():
        computed = pisano_period(m)
        assert computed == expected, f"pi({m})={computed}, expected {expected}"
    return True

def check_pisano_divisibility(m, period):
    """Verify that Fib(period) = 0 mod m and Fib(period+1) = 1 mod m."""
    a, b = 0, 1
    for _ in range(period):
        a, b = b, (a + b) % m
    return a == 0 and b == 1

# Verification
assert verify_known_pisano()

# Verify divisibility property for first 50 values
for m in range(2, 51):
    p = pisano_period(m)
    assert check_pisano_divisibility(m, p), f"Pisano verification failed for m={m}"

# Compute answer
N = 1000
periods = [0, 0] + [pisano_period(m) for m in range(2, N + 1)]
answer = sum(periods[2:])
print(answer)