Robert Eisele
Engineer, Systems Architect and DBA

Codefights: extendedFibonacci

Original Problem

You want to impress your friends with the Fibonacci Sequence, but they all know it already! Instead, you decide to make Fibonacci-like sequences as follows:

Given nonnegative integers \(a\) and \(b\), the sequence \(\{s_n\}_{n\geq 0}\) is defined as:

\(s_0=2\)

\(s_1=a\)

\(s_{n+2}=as_{n+1}+bs_n\)

Since you want to impress your friends, you should be able to quickly tell them \(s_i\) for any reasonable \(i\).

This value might be so large that you can't easily display it. Instead, output the value mod \(10^9 + 7\) (which is prime), in the range \([0,10^9+7)\).

Note that it is guaranteed that \(a^2+4b\) is a perfect square, and that calculation of this value will not overflow a double.

Example

  • For a = 1, b = 2 and i = 4, the output should be
    extendedFibonacci(a, b, i) = 17.
    s0 = 2
    s1 = a = 1
    sn + 2 = asn + 1 + bsn = sn + 1 + 2sn.
    s2 = 1 + 2 · 2 = 5
    s3 = 5 + 2 · 1 = 7
    s4 = 7 + 2 · 5 = 17

  • For a = 0, b = 15129 and i = 2831, the output should be
    extendedFibonacci(a, b, i) = 0.
    s1 = a = 0
    sn + 2 = asn + 1 + bsn = 15129sn
    s3 = 15129 · 0 = 0
    s5 = 15129 · 0 = 0
    ...
    s2831 = 15129 · 0 = 0

Input/Output

  • [time limit] 6000ms (groovy)
  • [input] integer64 a

    Along with \(b\), defines the sequence \(\{s_n\}_{n\geq 0}\)
    \(a^2+4b\) is a perfect square.
    \(0\leq a\leq 2^{26}\)

  • [input] integer64 b

    Along with \(a\), defines the sequence \(\{s_n\}_{n\geq 0}\)
    \(a^2+4b\) is a perfect square.
    \(0\leq b\leq 2^{26}\)

  • [input] integer64 i

    Index of the desired value in the sequence
    \(0\leq i\leq 2^{53}\)

  • [output] integer

    \(s_i \mod 10^9+7\)

Solution

We want to finda closed form solution for the extended fibonacci sequence \(s_n=as_{n-1}+bs_{n-2}\). To do that we try to express the sequence as \(s_n=kx^n\), which means the sequence is \(kx^n=akx^{n-1}+bkx^{n-2}\). Simplifying this equation yields \(x^2-ax-b=0\), which has the solutions \(x=\frac{a\pm\sqrt{a^2+4b}}{2}\). The sequence now reads as

\[s_n=k_1\left(\frac{a+\sqrt{a^2+4b}}{2}\right)^n + k_2\left(\frac{a-\sqrt{a^2+4b}}{2}\right)^n\]

We can now use the base cases to solve for \(k_1, k_2\):

\[s_0=k_1\left(\frac{a+\sqrt{a^2+4b}}{2}\right)^0 + k_2\left(\frac{a-\sqrt{a^2+4b}}{2}\right)^0=2\]

\[s_1=k_1\left(\frac{a+\sqrt{a^2+4b}}{2}\right)^1 + k_2\left(\frac{a-\sqrt{a^2+4b}}{2}\right)^1 = a\]

From the first equation follows that \(k_1+k_2=2\) and using it to solve the second equation reveals that \(k_1=k_2=1\). It follows that the closed form solution under the modular congruence is:

\[s_n\equiv \left(\frac{a+\sqrt{a^2+4b}}{2}\right)^n + \left(\frac{a-\sqrt{a^2+4b}}{2}\right)^n\pmod{10^9+7}\]

Implementig the congruence is then quite simple:

M = 10**9 + 7
extendedFibonacci = lambda a, b, i: \
    sum(pow(int(a + k * (a * a + 4 * b)**.5) / 2, i, M) for k in (-1, 1)) % M

« Back to problem overview