nth convolved Fibonacci numbers of order 6 modulo m

Question

Problem: Find the coefficient of x^k in (1−x−x²)^-6 modulo m.

Constraints:
k≤2⁶⁴
m≤10⁵, m can be a composite number.
I have 10^5 such queries to process in 2 sec, so O(log k) for each query solution will work.
kth Fibonacci and Lucas numbers can be calculated in O(log k).

My Approach: I thought that closed form expression may not be possible(I have not figured out any idea till now also), but some recursive formula or algorithm may be possible.

What I have found: On OEIS , I came to know that this reciprocal polynomial is generating function of convolved Fibonacci number of order 6 .
Then I have found this paper https://cs.uwaterloo.ca/journals/JIS/VOL7/Moree/moree12.pdf in which required answer is represented as sum of Fibonacci and Lucas numbers divided by powers of 5.

This is problematic since m can be a composite number(multiple of 5). I am stuck here because multiplicative inverse of powers of 5 will not exist in that case.

Please suggest me any solution for this or any other way to calculate the answer.

Thanks in advance.

Answer 1

I think you've almost got it. You just need to be careful about how you clear denominators.

For example, the paper you linked to gives the identity

$$50F^{(3)}_j = 5(j + 1)(j + 2)F_{j+3} + 6(j + 1)L_{j+2} + 12F_{j+1} \, .$$

In order to compute, $F^{(3)}_j \bmod m$, start by computing the quantity $$Q=\left(5(j + 1)(j + 2)F_{j+3} + 6(j + 1)L_{j+2} + 12F_{j+1}\right) \bmod 50m \, .$$

By construction, we know that $Q$ is the unique integer with $0 \leq Q < 50m$ such that $Q+50mk=50F^{(3)}_j$ for some integer $k$. By dividing these two relations through by $50$, it follows that $Q$ is a multiple of $50$, that $0 \leq Q/50 < m$, and that $Q/50+mk=F^{(3)}_j$. But this precisely means that $Q/50 = F^{(3)}_j \bmod m$.

You'll be able to do the same thing to get $F^{(6)}_j$; you'll just have to divide by a larger number (namely $5^5(5!)=375000$ instead of $5^2(2!)=50$). But it shouldn't be too large for your purposes, I think...

Answer 2

Here's one way you can solve general problems like this (for sequences that say, might not appear on the OEIS). The Taylor expansion of $(1-x-x^2)^{-6}$ looks like

$$(1-x-x^2)^{-6} = a_0 + a_1x + a_2x^2 + \dots$$

for some coefficients $a_i$. It therefore must hold that

$$1 = (1-x-x^2)^{6}(a_0 + a_1x + a_2x^2 + \dots)$$

Now, $(1-x-x^2)^6$ is some polynomial of degree 12, namely

$$x^{12}+ 6x^{11} + 9x^{10} - 10x^9 - 30x^8 + 6x^7 +41x^6 - 6x^5 - 30x^4 + 10x^3 + 9x^2 - 6x + 1$$

so by equating coefficients, it follows that for all $n\geq 1$

$$a_{n-12} + 6a_{n-11} + 9a_{n-10} - 10a_{n-9} - 30a_{n-8} + 6a_{n-7} + 41a_{n-6} - 6a_{n-5} - 30a_{n-4} + 10a_{n-3} + 9a_{n-2} - 6a_{n-1} + a_{n} = 0$$

and in particular

$$a_{n} = -(a_{n-12} + 6a_{n-11} + 9a_{n-10} - 10a_{n-9} - 30a_{n-8} + 6a_{n-7} + 41a_{n-6} - 6a_{n-5} - 30a_{n-4} + 10a_{n-3} + 9a_{n-2} - 6a_{n-1})$$

Now you have a degree 12 recurrence for $a_{n}$. Unfortunately, this might still be too slow to compute $a_{2^{64}}$ directly. Luckily, you can speed things up via fast matrix exponentiation.

Note that

$$\begin{bmatrix} a_{n+1} \\ a_{n} \\ \vdots \\ a_{n-10} \\ a_{n-11} \end{bmatrix} = M\begin{bmatrix} a_{n} \\ a_{n-1} \\ \vdots \\ a_{n-11} \\ a_{n-12} \end{bmatrix}$$

where

$$M = \begin{bmatrix} 6 & -9 & -10 & 30 & 6 & -41 & -6 & 30 & 10 & -9 & -6 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix} $$

In particular,

$$\begin{bmatrix} a_{n+k} \\ a_{n+k-1} \\ \vdots \\ a_{n+k-11} \\ a_{n+k-12} \end{bmatrix} = M^k\begin{bmatrix} a_{n} \\ a_{n-1} \\ \vdots \\ a_{n-11} \\ a_{n-12} \end{bmatrix}$$

You can compute $M^k$ in $O(\log k)$ matrix multiplications by repeated squaring (of course, taking everything modulo $m$ as you go along). Then, by multiplying $M^k$ to the vector containing the first $12$ coefficients $a_i$, you can find $a_k$.