Detailed mathematical approach

Problem Summary

Let \(\pi(n)\) denote the Pisano period of the Fibonacci sequence modulo \(n\), meaning the smallest positive period of the pair \((F_m,F_{m+1})\) modulo \(n\). For each positive integer \(p\), define \(M(p)\) as the largest integer \(n\) such that \(\pi(n)=p\), and set \(M(p)=1\) when no such \(n\) exists.

The problem asks for

$P(n)=\prod_{p=1}^{n} M(p),$

with the specific target

$P(10^6)\bmod 1{,}234{,}567{,}891.$

A brute-force search over moduli and periods would be far too slow. The implementation instead starts from a structural classification of which period lengths can appear as maximal Pisano periods.

Mathematical Approach

The key mathematical reduction used by the implementation is that almost every factor \(M(p)\) is trivial, and the nontrivial factors can be written directly in terms of Fibonacci and Lucas numbers.

Step 1: Separate the trivial period lengths

The implementation relies on the following classification:

$M(2)=1,\qquad M(3)=2,$

and for every odd \(p>3\),

$M(p)=1.$

So odd indices contribute nothing except \(p=3\). That already collapses the product to one special odd factor and a family of even factors.

Step 2: Express every nontrivial even factor explicitly

Write the Fibonacci and Lucas sequences as

$F_0=0,\quad F_1=1,\quad F_k=F_{k-1}+F_{k-2}\quad (k\ge 2),$

$L_0=2,\quad L_1=1,\quad L_k=L_{k-1}+L_{k-2}\quad (k\ge 2).$

For every \(k\ge 2\), the maximal modulus with Pisano period \(2k\) is given by

$M(2k)= \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$

This rule is exactly what the implementation uses. A few small values make the pattern concrete:

$M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(18)=L_9=76.$

Step 3: Rewrite the whole product

Once the odd factors are simplified, the product for \(n\ge 3\) becomes

$P(n)=M(3)\prod_{k=2}^{\lfloor n/2\rfloor} M(2k).$

Since \(M(3)=2\), this is

$P(n)=2\prod_{k=2}^{\lfloor n/2\rfloor} \begin{cases} L_k,& k\equiv 1 \pmod 2,\\ F_k,& k\equiv 0 \pmod 2. \end{cases}$

That formula removes all period searching. The remaining task is only to generate Fibonacci and Lucas values in order and multiply the correct one at each step.

Step 4: Turn the formula into a streaming recurrence

Recomputing \(F_k\) or \(L_k\) from scratch for every \(k\) would waste time. Instead, because both sequences satisfy the same second-order recurrence, we can advance them together in one forward pass:

$F_{k}=F_{k-1}+F_{k-2},\qquad L_{k}=L_{k-1}+L_{k-2}.$

At step \(k\), only the two most recent Fibonacci values and the two most recent Lucas values are needed. After advancing once, the algorithm multiplies the running answer by \(L_k\) when \(k\) is odd and by \(F_k\) when \(k\) is even, always reducing modulo \(1{,}234{,}567{,}891\).

Worked Example: \(P(10)\)

The sample checkpoint used by the implementation is easy to recover from the closed form.

For \(1\le p\le 10\), the nontrivial factors are

$M(3)=2,\qquad M(4)=F_2=1,\qquad M(6)=L_3=4,\qquad M(8)=F_4=3,\qquad M(10)=L_5=11.$

All remaining factors are \(1\). Therefore

$\begin{aligned} P(10) &=M(1)M(2)\cdots M(10)\\ &=1\cdot 1\cdot 2\cdot 1\cdot 1\cdot 4\cdot 1\cdot 3\cdot 1\cdot 11\\ &=264. \end{aligned}$

This matches the value produced by the implementation.

How the Code Works

The C++, Python, and Java implementations all use the same plan. They first handle the exceptional factor \(M(3)=2\) when \(n\ge 3\). Then they iterate \(k\) from \(1\) to \(\lfloor n/2\rfloor\), maintaining consecutive Fibonacci and Lucas terms modulo the required modulus.

Beginning with the first nontrivial step \(k=2\), each iteration advances both recurrences once. If \(k\) is odd, the current Lucas term is multiplied into the running product; if \(k\) is even, the current Fibonacci term is used instead. Because every multiplication is reduced immediately modulo \(1{,}234{,}567{,}891\), the computation stays bounded and never needs big-integer storage of the full product.

Complexity Analysis

The loop runs for exactly \(\lfloor n/2\rfloor\) iterations. Each iteration performs a constant amount of work: a few modular additions, one parity test, and at most one modular multiplication. Therefore the running time is \(O(n)\), and the memory usage is \(O(1)\).

For \(n=10^6\), this means only about \(500{,}000\) recurrence steps, which is easily practical.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=854
2. Pisano period: Wikipedia - Pisano period
3. Fibonacci number: Wikipedia - Fibonacci number
4. Lucas number: Wikipedia - Lucas number