Problem #459

Convergents of infinite sum
Public 02/12/18 9xp Math 100.0%

Define a sequence $b_n$ as below: $b_0 = c, b_n = b_{n-1}^2 – 2 (n \ge 1)$, where $c$ is a positive integer greater than or equal to 3.

Let infinite sum $s$ be \[ s = \sum\limits_{n = 0}^\infty \frac{1}{\prod\nolimits_{k = 0}^n {b_k}} = \frac{1}{b_0} + \frac{1}{{b_0}{b_1}} + \frac{1}{{b_0}{b_1}{b_2}} + \frac{1}{{b_0}{b_1}{b_2}{b_3}} + \cdots \] It can be proved that the infinite sum is convergent and is an irrational number for all possible values of $c$.

$s$ can be represented as an infinite continued fraction and corresponding convergents are denoted by $p_n/q_n$ ($n \ge 0$, $p_n$ and $q_n$ are coprime). For example, for $c$ = 6, $s$ = 0.1715728752…, and the first several convergents are $p_0/q_0$ = 0/1, $p_1/q_1$ = 1/5, $p_2/q_2$ = 1/6, $p_3/q_3$ = 5/29 and so on.

Let $P(c, n)$ and $Q(c, n)$ be numerator and denominator of the $n$th convergents $p_n/q_n$ of $s$ with value $c$, respectively. For instance, $P(6, 3)$ = 5, $Q(6, 3)$ = 29. Given Fibonacci sequence fn defined as $f_1 = 1$, $f_2 = 1$, $f_n = f_{n-1} + f_{n-2}$ ($n \ge 3$). The value of this sequence is no less than 3 from the 4th item.

Let the sum $SP(m, n) = \sum_{i = 4}^m P(f_i, n)$ and $SQ(m, n) = \sum_{i = 4}^m Q(f_i, n)$. You are given $SP(5, 10)$ = 606, $SQ(5, 10)$ = 2784, $SP(10, 100) \mod 1000000007$ = 774200907, $SQ(10, 100) \mod 1000000007$ = 830200702.

Find $SP(10^5, 10^{18})$ and $SQ(10^5, 10^{18})$, both modulo 1000000007.

Answer format: [$SP(10^5, 10^{18})$],[$SQ(10^5, 10^{18})$]

Example: 774200907,830200702 for $SP(10, 100)$ and $SQ(10, 100)$


Thanks to czp for the idea.



You need to be a member to keep track of your progress.
Register


Time may end, but hope will last forever.

Other Challenge Sites

Contact

elasolova
[64][103][109][97][105][108][46][99][111][109]