theVPN's blog

A pretty cool Fibonacci sequence problem
By theVPN, history, 3 years ago, In English

Hey there,

I just took a programming contest and received a pretty interesting mathematical problem.

To sum up, you are given two numbers n and k (1 <= n <= 10^18, 1 <= k <= 10^6).

Assume that F(i) is the i-th number in the Fibonacci sequence

E.g: F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, e.t.c.

Calculate the sum S of the first n Fibonacci numbers raised to the power of k.

Or in terms of pseudocode:

S = 0
for (i = 1 -> n)
    S = S + F(i)^k

Print the answer modulo 998244353. Is there any good approach to this problem? Thank you for reading!

  • Vote: I like it
  • +30
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Do you have a link to the task? I'd like to try a few things

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

You can try to find polinom with degree k. You take first k Fibonacci and build Lagrange or Newton polinom. Then find F(n). Tbh I'm not sure if it will work but I think it will. Similar problem was here

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Pretty sure this does not work because unlike $$$\sum_{x = 0}^{n} x^{k}$$$, the result of this sum $$$\sum_{x = 0}^{n} F^{k}(x)$$$ is not a polynomial of any degree. Even when $$$k = 1$$$ it is well known that $$$\sum_{x = 0}^{n} F(x) = F(n + 2) - 1$$$ is not a polynomial. Unless there is some generalization of Lagrange interpolation that I am not aware of, I don't think it's possible to solve it this way (would love to be proven wrong!)

    → Reply
»
3 years ago, hide # |
← Rev. 3  
Vote: I like it +74 Vote: I do not like it

From Binet's formula, we know that

$$$ F_n = \frac{\phi^n - \psi^n}{\sqrt 5} $$$

, where $$$\phi = \frac{1 + \sqrt 5}{2}$$$ and $$$\psi = \frac{1 - \sqrt 5}{2}$$$.

Using that, let's expand $$$F_n^k$$$ using Newton's binomial theorem:

$$$ \begin{align} F_n^k &= \left( \frac{\phi^n - \psi^n}{\sqrt 5} \right)^k \\ &= \frac{\left( \phi^n - \psi^n \right)^k}{(\sqrt 5)^k} \\ &= \frac{1}{(\sqrt 5)^k} \sum_{i=0}^k \binom{k}{i} (-1)^i (\phi^n)^i (\psi^n)^{k-i} \\ \end{align} $$$

Next, let's expand $$$S$$$:

$$$ \begin{align} S &= \sum_{j=1}^n F_j^k \\ &= \sum_{j=1}^n \frac{1}{(\sqrt 5)^k} \sum_{i=0}^k \binom{k}{i} (-1)^i (\phi^j)^i (\psi^j)^{k-i} \\ &= \sum_{j=1}^n \frac{1}{(\sqrt 5)^k} \sum_{i=0}^k \binom{k}{i} (-1)^i (\phi^i \psi^{k-i})^j \\ &= \frac{1}{(\sqrt 5)^k} \sum_{i=0}^k \binom{k}{i} (-1)^i \left( \sum_{j=1}^n (\phi^i \psi^{k-i})^j \right) \\ \end{align} $$$

Note that for each fixed $$$i$$$, the only sum we need to evaluate is $$$\sum_{j=1}^n A_i^j$$$, where $$$A_i = \phi^i \psi^{k-i}$$$. This problem has a well-known solution with complexity $$$\mathcal O(\log n)$$$, see ABC 293E. Therefore, we obtained an algorithm with a time complexity of $$$\mathcal O(k \log n)$$$.

At this point, we only need to evaluate $$$\sqrt 5$$$ modulo $$$p$$$, then we can use it to directly evaluate $$$(\sqrt 5)^k$$$, $$$\phi$$$, $$$\varphi$$$, and $$$A_i$$$. In ZOJ-3774, $$$p = 10^9 + 9$$$, and "fortunately" such number exist: $$$383008016^2 \equiv 5 \pmod {10^9 + 9}$$$, so $$$383008016 \equiv \sqrt 5 \pmod {10^9 + 9}$$$. There are other unfortunate value of $$$p$$$ however, and $$$998244353$$$ is one of them (To determine whether a value of $$$p$$$ is fortunate or not, see Legendre symbol).

So how do we solve this? We simply does not care about evaluating $$$\sqrt 5$$$ at all!. Instead, we will work with numbers in the extension field of $$$\mathbb Z_p$$$:

$$$ \mathbb Z_p(\sqrt 5) = \{ a + b \sqrt 5 \mid a, b \in \mathbb Z_p \} $$$

We will denote $$$a + b \sqrt 5$$$ as $$$\langle a, b \rangle$$$. So

  • $$$1 = \langle 1, 0 \rangle$$$.
  • $$$\sqrt 5 = \langle 0, 1 \rangle$$$.
  • $$$\phi = \left\langle \frac{1}{2}, \frac{1}{2} \right\rangle$$$.
  • $$$\psi = \left\langle \frac{1}{2}, \frac{-1}{2} \right\rangle$$$.

Arithmetic operations can still be performed on these numbers. You can try to figure it out yourself — addition, subtraction and multiplication should be easy enough, but if you got stuck on division, here is a hint:

$$$ \frac{\langle a, b \rangle}{\langle c, d \rangle} = \frac{\langle a, b \rangle \langle a, -b \rangle}{\langle c, d \rangle \langle c, -d \rangle}$$$
→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +18 Vote: I do not like it

    By the way, another solution for the division is that in $$$\mathbb{F}_{p^2} = \mathbb{F}_{p}\left(\sqrt{5}\right)$$$, we always have $$$a^{p^2} \equiv a \pmod{p^2}$$$.

    So, if $$$a \neq \left \lt 0, 0\right \gt $$$, then $$$a^{p^2 - 1} \equiv \left \lt 1, 0\right \gt \pmod p$$$, and of course, $$$\dfrac{1}{\left \lt c, d\right \gt } \equiv \left \lt c, d\right \gt ^{p^2 - 2} \pmod p$$$

    → Reply