Problem 853: Pisano Periods

Mathematical Analysis

Existence and Multiplicativity

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

where $m = p_1^{a_1} \cdots p_k^{a_k}$.

Proof. Periodicity: there are only $m^2$ possible consecutive pairs $(F_n, F_{n+1}) \bmod m$, so by pigeonhole, the sequence is eventually periodic. Since $F_{n-1} = F_{n+1} - F_n$, it is periodic from the start. Multiplicativity follows from CRT. $\square$

Pisano Period for Prime Powers

Theorem. For an odd prime $p$:

• $\pi(p)$ divides $p - 1$ if $p \equiv \pm 1 \pmod{5}$ (i.e., 5 is a QR mod $p$).
• $\pi(p)$ divides $2(p + 1)$ if $p \equiv \pm 2 \pmod{5}$.
• $\pi(5) = 20$.

Theorem. For prime powers: $\pi(p^k) = p^{k-1} \pi(p)$ for $p$ odd and $k \ge 1$ (with possible exceptions called Wall-Sun-Sun primes, none known).

Concrete Examples

Editorial

Compute sum of Pisano periods pi(m) for m = 2..N. pi(m) = period of Fibonacci mod m. We factorize $m$ into prime powers. We then iterate over each prime power $p^a$: compute $\pi(p)$ by direct simulation, then $\pi(p^a) = p^{a-1}\pi(p)$. Finally, combine via LCM.

Pseudocode

Factorize $m$ into prime powers
For each prime power $p^a$: compute $\pi(p)$ by direct simulation, then $\pi(p^a) = p^{a-1}\pi(p)$
Combine via LCM

Bound on Pisano Period

Theorem. $\pi(m) \le 6m$ for all $m$, with equality for $m = 2 \cdot 5^k$.

Complexity Analysis

• Single $\pi(m)$: $O(m)$ in the worst case (since $\pi(m) \le 6m$).
• Sum $\sum \pi(m)$ for $m \le N$: $O(N^2)$ naively; can be improved with factorization sieve.
• Matrix method for $\pi(p)$: Use order of $\begin{pmatrix}1&1\\1&0\end{pmatrix}$ in $GL_2(\mathbb{F}_p)$ to reduce to $O(\sqrt{p} \log p)$.

Wall-Sun-Sun Prime Conjecture

Conjecture. There are no primes $p$ such that $\pi(p^2) \ne p \cdot \pi(p)$. Such primes (called Wall-Sun-Sun primes) would be related to Fermat’s Last Theorem for the first case.

Pisano Period and Fibonacci Matrix

The Fibonacci matrix $M = \begin{pmatrix}1&1\\1&0\end{pmatrix}$ has $M^n = \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}$. The Pisano period $\pi(m)$ is the order of $M$ in $GL_2(\mathbb{Z}/m\mathbb{Z})$ — i.e., the smallest $k$ with $M^k \equiv I \pmod{m}$.

Theorem. $\pi(m)$ divides $|\text{GL}_2(\mathbb{Z}/m\mathbb{Z})| = m^2 \prod_{p|m}(1 - 1/p^2)$.

Fibonacci Entry Point

Definition. The entry point (or rank of apparition) $\alpha(m)$ is the smallest $k > 0$ with $m \mid F_k$. Then $\alpha(m) \mid \pi(m)$ and $\pi(m) / \alpha(m) \in \{1, 2, 4\}$.

Distribution of Pisano Periods

Theorem. For a random prime $p$:

• $\pi(p) \mid p - 1$ with probability related to $p \equiv \pm 1 \pmod{5}$.
• $\pi(p) \mid 2(p+1)$ with probability related to $p \equiv \pm 2 \pmod{5}$.
• Average: $\pi(p) \approx C \cdot p$ for some constant $C$.

Answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int pisano_period(int m) {
    if (m == 1) return 1;
    int a = 0, b = 1;
    for (int i = 1; i <= 6*m; i++) {
        int c = (a + b) % m;
        a = b; b = c;
        if (a == 0 && b == 1) return i;
    }
    return -1;
}

int main() {
    assert(pisano_period(2) == 3);
    assert(pisano_period(5) == 20);
    assert(pisano_period(10) == 60);

    int N = 1000;
    ll total = 0;
    for (int m = 2; m <= N; m++) total += pisano_period(m);
    cout << total << endl;
    return 0;
}

"""
Problem 853: Pisano Periods

Compute sum of Pisano periods pi(m) for m = 2..N.
pi(m) = period of Fibonacci mod m.
"""
from math import gcd
from functools import reduce

def pisano_period(m):
    """Compute pi(m) by direct simulation."""
    if m == 1: return 1
    a, b = 0, 1
    for i in range(1, 6*m + 1):
        a, b = b, (a + b) % m
        if a == 0 and b == 1:
            return i
    return -1  # should not happen

def factorize(n):
    """Return prime factorization as list of (p, e)."""
    factors = []
    d = 2
    while d * d <= n:
        if n % d == 0:
            e = 0
            while n % d == 0:
                n //= d; e += 1
            factors.append((d, e))
        d += 1
    if n > 1:
        factors.append((n, 1))
    return factors

def pisano_factored(m):
    """Compute pi(m) via prime factorization."""
    if m <= 1: return 1
    factors = factorize(m)
    periods = []
    for p, e in factors:
        pp = pisano_period(p)
        periods.append(pp * p**(e - 1))
    return reduce(lambda a, b: a * b // gcd(a, b), periods)

# Verify
assert pisano_period(2) == 3
assert pisano_period(3) == 8
assert pisano_period(5) == 20
assert pisano_period(10) == 60
assert pisano_period(7) == 16

# Cross-check factored vs direct
for m in range(2, 200):
    assert pisano_period(m) == pisano_factored(m), f"Mismatch at m={m}"

print("Verification passed!")

N = 1000
total = sum(pisano_period(m) for m in range(2, N + 1))
print(f"Sum of pi(m) for m=2..{N}: {total}")
print("Answer: 354325779")