recursion - what is an efficient algorithm for solving recurrence relation for 2nd order problems? -

i want solve recurrence relation quadratic term in it.

for example.. t(n)= t(n-1)^2 + t(n-1) + 2 recurrence relation , have print sum mod 100000.

how can if without using simple brute-force method?

depending on how big n can (say, around 10,000,000), may away simple for loop run in small time (e.g. around second).

i can't tell if find mathematical formula generic t(1) and/or generic recursion, guess can't. nevertheless, tell of mathematical property solve problem. called congruence. in short, syntax:

a =(15)= b 

means 15 divides b - a. actual mathematical symbol = 3 lines , number written above it, can't type it!

now here couple of theorems useful you:

1.

a =(n)= b  \             > => =(n)= c b =(n)= c  / 

2.

a =(n)= b  =>  a+c =(n)= b+c 

3.

a =(n)= b  =>  a*c =(n)= b*c 

4.

a =(n)= b  =>  a^2 =(n)= b^2 

they can proved writing a , b as:

a = k1*n+r b = k2*n+r 

and apply transformations , make sure in end, b - a still divisible n.

---

that said, algorithm becomes follows (assuming want sum of t1 tn mod m):

t = 3        /* initial t1 */ tsum = t     /* initial sum */  i=1 n     t = (t^2 % m + t + 2) % m     tsum = (tsum + t) % m 

the important thing notice here t , tsum bounded m , maximum intermediate result expression t^2 (for non-trivial ms) can take maximum of (m-1)^2.

therefore, in implementation, don't need deal large numbers, merely datatype large enough hold (m-1)^2. in c, uint64_t do. note m=100000, (m-1)^2 doesn't fit in 32-bit integer.

this algorithm o(n) way, unless n large or unless it's in frequent loop, should fast enough daily needs!

---

edit

the problem can solved in o(m) rather o(n). due fact t(i) in range of [0, m-1) , therefore computing upto t(m+1), cycle back. since t(n) depends solely on t(n-1), getting repeated value t(n-1) result in same chain of values first time.

so, let's unroll t , tsum better observe how can exploited. assume t generates values a, b, ..., z , after z, cycles k , after couple of cycles finishes on p (because reached n):

t      b   c   d   e   ... k   ...  z   k   ... z   k   ... z   ... k   ... p tsum  bs  cs  ds  es  ... ks  ...  zs  ks2 ... zs2 ks3 ... zs3 ... kst ... pst 

so goal calculate pst. idea calculate ks2, take difference ks, multiply t , add ks kst. add remaining pst.

the algorithm follows:

sums=[m times 0]    /* initially, no sum calculated */ indices=[m times 0] /* indices[i] = means sums[i] corresponds t(1)+...+t(i) */ t = 3           /* initial t1 */ tsum = t        /* initial sum */ sums[t] = tsum indices[t] = 1  i=2 n     t = (t^2 % m + t + 2) % m     if sums[t] != 0         /* loop detected */         break      tsum = (tsum + t) % m     sums[t] = tsum     indices[t] =  if == n     return tsum  /* compute how many cycles */ cycle_length = - indices[t] t = (n - indices[t]) / cycle_length  /* add sum of cycles */ tsum = (sums[t] + t * (tsum - sums[t])) % m  /* add left */ i=indices[t] + t * cycle_length+1 n     t = (t^2 % m + t + 2) % m     tsum = (tsum + t) % m 

note: there may off-by-one errors in index calculations. if plan on using algorithm, double check make sure doesn't miss t(i) or sum twice.