Primonacci

For any positive integer $n$ the function $\operatorname{next\_prime}(n)$ returns the smallest prime $p$ such that $p \gt n$.

The sequence $a(n)$ is defined by:
$a(1)=\operatorname{next\_prime}(10^{14})$ and $a(n)=\operatorname{next\_prime}(a(n-1))$ for $n \gt 1$.

The Fibonacci sequence $f(n)$ is defined by:
$f(0)=0$, $f(1)=1$ and $f(n)=f(n-1)+f(n-2)$ for $n \gt 1$.

The sequence $b(n)$ is defined as $f(a(n))$.

Find $\sum b(n)$ for $1 \le n \le 100\,000$.
Give your answer mod $1234567891011$.

This problem is a combination of number theory and dynamic programming. We are given three sequences. The first sequence is just the sequence of prime numbers, starting from some unspecified prime number larger than $10^{14}$.

The second sequence is the Fibonacci sequence, which is well known and can be computed efficiently using dynamic programming. Specifically, we can compute each number of the Fibonacci sequence from the two previous numbers, starting from $f(0)=0$ and $f(1)=1$.

The more unusual requirement is that the third sequence, $b(n)$, is defined to be $f(a(n))$. This means that we must compute the $a(n)$-th Fibonacci number for each $n$.

Calculating prime numbers in general can be difficult. However, the next part of the problem requires us to find the sum of the first $10^5$ terms of the sequence $b(n)$, and this sum should be taken modulo $1234567891011$.

The sum of a sequence modulo some number m is just the sum of the sequence of the numbers modulo m. So we have

$$\sum_{n=1}^{100000} b(n) \mod 1234567891011 = \sum_{n=1}^{100000} f(a(n)) \mod 1234567891011$$

As we see, we need to find $f(a(n)) \mod 1234567891011$ for each $n$.

Calculating Fibonacci numbers modulo m can also be done efficiently using dynamic programming. We calculate each such number from the two previous ones, exactly as in the standard computation of the Fibonacci sequence, but now each number is reduced modulo m immediately after it is computed.

However, calculating the Fibonacci sequence for terms as large as $10^{14}$ is not feasible because the Fibonacci sequence grows exponentially. Instead, we can use the fact that the Fibonacci sequence, when taken modulo m, is periodic. The period, known as the Pisano period, is at most $m^2$.

Although there are ways to directly calculate the Pisano period, it’s not feasible to compute it for large m (as required by the problem), because these methods are more complicated and involve more computation. A simpler way is to calculate Fibonacci numbers modulo m until the sequence repeats. For large m, even this simple method can take a long time, but we can speed it up using dynamic programming.

After computing the Pisano period, we can compute $f(a(n)) \mod 1234567891011$ by calculating $a(n)$ modulo the period and then looking up the corresponding Fibonacci number modulo $1234567891011$ in the precomputed table.

The required sum is then the sum of these numbers, again reduced modulo $1234567891011$.

Without a computational tool, this problem is not solvable because the operations involved are large and it’s time-consuming. Some steps of the problem involve a process which is not computationally feasible and finding the next prime greater than $10^{14}$ might take a quite long time. For instance, calculating the Fibonacci sequence for terms as large as $10^{14}$, isn’t possible because of the very nature of the Fibonacci sequence. It grows exponentially, and even with modern computing facilities, it’s not feasible to calculate such large terms.

So, It’s not possible to provide a numerical answer in this platform without knowing the exact value of $a(1) = \operatorname{next\_prime}(10^{14})$ and taking some computational assistance.

More Answers: