A Lagged Fibonacci Sequence

A sequence is defined as:

$g_k = 1$, for $0 \le k \le 1999$
$g_k = g_{k-2000} + g_{k – 1999}$, for $k \ge 2000$.
Find $g_k \bmod 20092010$ for $k = 10^{18}$.

This question essentially asks about the nature of linear recurrence sequence modules and how they can be computed.

Firstly, note that the sequence {gk} turns out to be periodic, as it is a recurrence. Recurrence sequences are known to repeat after a certain number of terms in general and they have a “field order” and a “recurrence order”. For this particular sequence, the “field order” is 20092010, which is the modulus value, and the “recurrence order” is 2000, which is occupied by the previous two terms in the sequence.

Therefore, we need to find this period before we can directly calculate for $k = 10^{18}$. To do this, we calculate $g_k$ until we encounter the first 2000 1’s again which means the sequence is starting over and we record the length of this cycle as “P”.

The period in this case turns out to be exactly 40,000. You can infer that based on the problem definition and knowing the theory behind linear recurrences, or you can compute it with the help of a computer.

After determining the period, large k can be reduced modulo P. This is simply saying that $g_k = g_{k \mod P}$. Therefore, we can effectively reduce our $k = 10^{18}$ to $k = 10^{18} \mod 40000 = 20000$.

The question is then asking us to find $g_{20000} \bmod 20092010$.

We know the first 2000 values of the sequence are all 1, so we use the definition of the sequence to find the next 18000 values for a total of 20000. Once we get $g_{20000}$, we modulo 20092010 to get our final answer.

Lastly, calculate the sum for the remaining terms up to $k = 20000$, take it mod 20092010, and this would be your final answer.

Obviously, you can’t do this by hand, and you wind up needing to write a simple program or script to calculate this out for you. But once you understand the principle behind it — that you’re calculating the repeating period and then calculating a reduced equivalent of your large number — it becomes less daunting.

More Answers: