Solution

Answer: 29894398

Let $\pi(n)$ denote the Pisano period modulo $n$, and define

$$M(p)=\max{n:\pi(n)=p},$$

with $M(p)=1$ if no such $n$ exists.

We must compute

$$P(10^6)=\prod_{p=1}^{10^6} M(p)\pmod{1234567891}.$$

1. Mathematical analysis

The key facts about Pisano periods are:

A. Pisano periods and Fibonacci divisibility

A classical identity is:

$$\pi(n)=\text{ord}_n \begin{pmatrix} 1&1\1&0 \end{pmatrix}.$$

Another important result is:

$$N(p):=\max{n:\pi(n)\mid p} = \gcd(F_p,F_{p+1}-1),$$

where $F_k$ is the Fibonacci sequence.

For even periods this simplifies dramatically.

B. Closed form for $N(2m)$

Using Fibonacci/Lucas identities:

$$\gcd(F_{2m},F_{2m+1}-1)= \begin{cases} F_m, & m \text{ even},\ L_m, & m \text{ odd}, \end{cases}$$

where $L_m$ is the Lucas sequence:

$$L_0=2,\quad L_1=1,\quad L_n=L_{n-1}+L_{n-2}.$$

Hence

$$N(2m)= \begin{cases} F_m,&m\text{ even},\ L_m,&m\text{ odd}. \end{cases}$$

The crucial extra fact is that these numbers actually attain period exactly $2m$, so:

$$M(2m)=N(2m).$$

C. Odd periods

For every $n>2$, the Pisano period is even.

The only odd Pisano period that occurs is:

$$\pi(2)=3.$$

Therefore:

$$M(3)=2,$$

and for every odd $p>3$,

$$M(p)=1.$$

So the entire product reduces to even periods only.

2. Final formula

For $p=2m$ with $m\ge3$,

$$M(2m)= \begin{cases} F_m,&m\text{ even},\ L_m,&m\text{ odd}. \end{cases}$$

Thus

$$P(10^6) = 2 \prod_{m=3}^{500000} \begin{cases} F_m,&m\text{ even},\ L_m,&m\text{ odd} \end{cases} \pmod{1234567891}.$$

This is now straightforward to compute iteratively modulo $1234567891$.

3. Python implementation

MOD = 1234567891
TARGET = 1_000_000

def solve():
    # M(3) = 2
    result = 2

    max_m = TARGET // 2

    # Fibonacci:
    # F0 = 0, F1 = 1
    f_prev, f_cur = 0, 1

    # Lucas:
    # L0 = 2, L1 = 1
    l_prev, l_cur = 2 % MOD, 1 % MOD

    for m in range(2, max_m + 1):

        # advance Fibonacci
        f_prev, f_cur = f_cur, (f_prev + f_cur) % MOD

        # advance Lucas
        l_prev, l_cur = l_cur, (l_prev + l_cur) % MOD

        if m < 3:
            continue

        if m % 2 == 0:
            # M(2m) = F_m
            result = (result * f_cur) % MOD
        else:
            # M(2m) = L_m
            result = (result * l_cur) % MOD

    return result

print(solve())

4. Code walkthrough

Initialization

result = 2

accounts for:

$$M(3)=2.$$

Fibonacci iteration

f_prev, f_cur = 0, 1

stores consecutive Fibonacci numbers.

At each step:

f_prev, f_cur = f_cur, (f_prev + f_cur) % MOD

updates to the next Fibonacci number modulo $MOD$.

Lucas iteration

Similarly:

l_prev, l_cur = 2, 1

tracks Lucas numbers.

Multiplication step

For each $m\ge3$:

if $m$ is even, multiply by $F_m$,
otherwise multiply by $L_m$.

This exactly implements:

$$M(2m)= \begin{cases} F_m,&m\text{ even},\ L_m,&m\text{ odd}. \end{cases}$$

5. Verification on the sample

The problem states:

$$P(10)=264.$$

The nontrivial values are:

$$M(3)=2,\quad M(6)=4,\quad M(8)=3,\quad M(10)=11.$$

Hence

$$P(10)=2\cdot4\cdot3\cdot11=264,$$

which matches perfectly.

Also:

$$M(18)=L_9=76,$$

exactly as given.

6. Final computation

Running the program gives:

$$P(1,000,000)\bmod 1,234,567,891 = 29894398.$$

Answer: 29894398

Project Euler Problem 854