ROSECODE 240

Generalized Pisano Period 2

Min_25 · Math · 2015-05-07

Let $F_{k} (n)$ be a linear recurrence sequence such that $\begin{aligned} F_{k} (n) & = 1 (1 \leq n \leq k), \\ F_{k} (n) & = \sum_{i = 1}^{k} F_{k} (n - i) (n > k) . \end{aligned}$

For example, $F_{2} (1) = 1$ , $F_{2} (2) = 1$ and $F_{2} (3) = 2$

Let $P (k, m)$ be the (minimum) period of $F_{k} (n)$ modulo $m$ .

You are given that $P (2, 10) = 60$ and $P (2, 10^{9}) = 1 500 000 000$ .

Find $P (50, 10^{9})$ .

Note: The answer is a 29 digit number.

[My timing: 42 sec (PyPy)]