← RoseCode

ROSECODE 459

Convergents of infinite sum

liuguangxi · Math ·

Define a sequence bn as below: b0=c,bn=bn−12−2(n≥1), where c is a positive integer greater than or equal to 3.

Let infinite sum s be s=∑n=0∞1∏k=0nbk=1b0+1b0b1+1b0b1b2+1b0b1b2b3+⋯ 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 pn/qn (n≥0, pn and qn are coprime). For example, for c = 6, s = 0.1715728752..., and the first several convergents are p0/q0 = 0/1, p1/q1 = 1/5, p2/q2 = 1/6, p3/q3 = 5/29 and so on.

Let P(c,n) and Q(c,n) be numerator and denominator of the nth convergents pn/qn of s with value c, respectively. For instance, P(6,3) = 5, Q(6,3) = 29. Given Fibonacci sequence fn defined as f1=1, f2=1, fn=fn−1+fn−2 (n≥3). The value of this sequence is no less than 3 from the 4th item.

Let the sum SP(m,n)=∑i=4mP(fi,n) and SQ(m,n)=∑i=4mQ(fi,n). You are given SP(5,10) = 606, SQ(5,10) = 2784, SP(10,100)mod1000000007 = 774200907, SQ(10,100)mod1000000007 = 830200702.

Find SP(105,1018) and SQ(105,1018), both modulo 1000000007.

Answer format: [SP(105,1018)],[SQ(105,1018)]

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


Thanks to czp for the idea.