← RoseCode

ROSECODE 459

Convergents of infinite sum

liuguangxi · Math ·

Define a sequence bn as below: b0=c,bn=bn122(n1), where c is a positive integer greater than or equal to 3.

Let infinite sum s be s=n=01k=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 (n0, 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=fn1+fn2 (n3). 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.