Detailed mathematical approach

Problem Summary

For a modulus \(n\), the Fibonacci sequence reduced modulo \(n\) eventually becomes periodic, and \(\pi(n)\) denotes the length of its first full cycle. Problem 853 asks for

$\sum_{\substack{2 \le n \lt 10^9 \\ \pi(n)=120}} n.$

Testing every integer below \(10^9\) would be hopeless. The successful idea is to turn the period condition into a precise return-to-state test and then use divisibility of Fibonacci numbers to shrink the search space to a small divisor set.

Mathematical Approach

Write

$S_k(n)=\bigl(F_k \bmod n,\; F_{k+1} \bmod n\bigr).$

Because the Fibonacci recurrence is determined completely by two consecutive values, the Pisano period is the smallest positive integer \(T\) with \(S_T(n)=S_0(n)=(0,1)\).

Step 1: Rewrite the Period as a State Return

The pair \((F_k,F_{k+1})\) determines the entire future sequence, so the sequence modulo \(n\) restarts exactly when the pair \((0,1)\) reappears. Therefore \(T\) is a period modulo \(n\) if and only if

$F_T \equiv 0 \pmod n,\qquad F_{T+1} \equiv 1 \pmod n.$

To make \(T\) the exact Pisano period, not merely a multiple of it, no proper divisor \(d \mid T\) may satisfy the same pair of congruences.

Step 2: Use \(T=120\) to Force \(n \mid F_{120}\)

If \(\pi(n)=120\), then the first congruence immediately gives

$n \mid F_{120}.$

The implementations use the explicit factorization

$F_{120}=2^5 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 23 \cdot 31 \cdot 41 \cdot 61 \cdot 241 \cdot 2161 \cdot 2521 \cdot 20641.$

This is only a necessary condition, because we still must enforce \(F_{121}\equiv 1 \pmod n\) and minimality. But it is already powerful: every valid modulus must be a divisor of this single number, so no other prime factor can ever appear.

Step 3: Enumerate Only Divisors Below the Limit

From the factorization above, the number of divisors of \(F_{120}\) is

$\tau(F_{120})=(5+1)(2+1)2^{11}=36864.$

So before applying the bound \(n \lt 10^9\), there are only tens of thousands of structurally possible candidates instead of one billion integers. The implementations build these divisors multiplicatively, prime by prime, and retain only those below the problem limit.

Step 4: Distinguish “Period Divides 120” from “Period Equals 120”

Dividing \(F_{120}\) is not enough. A candidate modulus can satisfy \(F_{120}\equiv 0 \pmod n\) even when its true Pisano period is \(10\), \(20\), \(30\), \(40\), \(60\), or another proper divisor of \(120\). Exactness is recovered by requiring

$S_{120}(n)=(0,1),$

but also

$S_d(n)\ne(0,1)\qquad(d \mid 120,\ d \lt 120).$

That second condition is precisely the minimality test.

Step 5: Compute Fibonacci Pairs Quickly with Fast Doubling

The C++, Python, and Java implementations evaluate Fibonacci pairs modulo \(n\) using fast doubling. If \(m\ge 0\), then

$F_{2m}=F_m\bigl(2F_{m+1}-F_m\bigr),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$

These identities allow the index to be halved at each recursive step, so the pair \((F_k,F_{k+1})\bmod n\) is obtained in \(O(\log k)\) time. Since every check here uses \(k=120\) or a divisor of \(120\), the period test is extremely cheap.

Worked Example

The divisor \(11\) shows why the minimality test matters. Because \(11\mid F_{120}\), it survives candidate generation, and indeed

$S_{120}(11)=(0,1).$

However, the same reset already occurs at \(d=10\), so the true Pisano period modulo \(11\) is \(10\), not \(120\). Therefore \(11\) must be rejected.

By contrast, \(2521\) also divides \(F_{120}\) and satisfies \(S_{120}(2521)=(0,1)\), but none of the proper divisors of \(120\) returns to \((0,1)\) modulo \(2521\). Hence \(\pi(2521)=120\), so \(2521\) contributes to the final sum.

The small checkpoint built into the overall method works the same way: if the target period is changed to \(18\) and the search range is restricted to \(2 \le n \lt 50\), the only valid moduli are \(19\) and \(38\), and their sum is \(57\).

How the Code Works

The implementation first lists all proper divisors of \(120\), because those are exactly the indices needed for the exact-period rejection step. It then stores the prime factorization of \(F_{120}\) and generates all divisors below \(10^9\) by multiplying allowed prime powers cumulatively.

For each candidate modulus, the implementation computes the Fibonacci state at index \(120\). If the state is not \((0,1)\), the candidate is discarded immediately. If the state does return to \((0,1)\), the implementation repeats the same check for every proper divisor of \(120\). A candidate is accepted only when every smaller check fails.

This mirrors the mathematics exactly: divisor generation enforces the necessary condition \(n\mid F_{120}\), while the state tests upgrade that necessary condition to the exact statement \(\pi(n)=120\).

Complexity Analysis

Let \(C\) be the number of generated divisors below \(10^9\). The implementations never scan the full interval \([2,10^9)\); they inspect only this divisor list. From the factorization of \(F_{120}\), the theoretical upper bound before the cutoff is \(36864\) candidates.

Each candidate requires one Fibonacci-pair evaluation at \(120\) and one more for each proper divisor of \(120\). There are \(15\) proper divisors, and each evaluation costs \(O(\log 120)\). Therefore the total running time is \(O(C\log 120)\), which is effectively linear in the candidate count, and the memory usage is \(O(C)\).

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=853
2. Pisano period: Wikipedia - Pisano period
3. Fibonacci number: Wikipedia - Fibonacci number
4. Fast doubling identities for Fibonacci numbers: cp-algorithms - Fibonacci Numbers
5. Modular arithmetic: Wikipedia - Modular arithmetic