Efficient Computation of Sparse Fibonacci Subsequences

The Fibonacci sequence is defined as:
\(F_0 = 0, \ F_1 = 1,\) and \(F_n = F_{n-1} + F_{n-2}\) for \(n > 1\).

The first few elements of the sequence are:
\(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \ldots\)

Using the classical recurrence relation above, we need to know all preceding elements of the series up to \(n-1\) in order to obtain \(F_n\). For example, to compute \(F_{10} = 55\), we first calculate \(F_9 = 34\) and \(F_8 = 21\), which themselves depend on earlier values in the sequence.

Here, we aim to explore the possibility of generating an arbitrary subsequence of the Fibonacci sequence without the need to calculate all preceding terms. For example, we may be interested in computing only \(F_{100}\), \(F_{555}\), \(F_{1000}\), and \(F_{2000}\). Is it possible to compute these specific terms directly, without generating the entire sequence up to \(F_{2000}\)?
As we will see, this is indeed possible.

In the example below, we attempt to find one thousand Fibonacci numbers modulo $m$ for every 10th prime number greater than \(10^{15}\):

\[S = \{F_{p_{10k}} \bmod m \mid p_{10k} \text{ is the } 10k\text{-th prime number such that } p_{10k} > 10^{15}, \, 0 \leq k < 1000 \}.\]

Follow along in the Jupyter notebook below: