A mathmetical Recurrence

Matrix.code's blog

By Matrix.code, 9 years ago, In English

Here is the given information : 
Q1 = a; n = 1
Q2 = b; n = 2

Qn = n * ( 1 + Q(n-1))/ (Q(n-2))
// integer division 
n <= 10^15
a , b < 10^9

Input : a, b , n ;
Output : Qn 

How to solve it ??

math

Matrix.code
9 years ago
16

Comments (15)

Show archived | Write comment?

I_love_Captain_America

9 years ago, # |

Complexity has to be log(n) or better. Try matrix exponentiation somehow.

→ Reply

hellman_

9 years ago, # ^ |

Obviously recurrence is not linear so it can not be expressed as a matrix.

→ Reply

I_love_Captain_America

9 years ago, # ^ |

That is what I am confused about too. But say, if we divide Q(n-2) outside the exponentiation(somehow). Either that, or some formula is there to calculate in O(1). It would be cool if M.E. solution exists, better that finding the formula.

→ Reply

zxqfl

9 years ago, # |

+19

What should you do if Q(n - 2) is zero?

→ Reply

Matrix.code

9 years ago, # ^ |

-10

this will never 0..

→ Reply

Xellos

9 years ago, # ^ |

+14

a = 42, b = 1

$\text{[math]}$ (integer division)

→ Reply

Matrix.code

9 years ago, # ^ |

Input will be such that No term will be zero ...

→ Reply

Auster

9 years ago, # |

There is the similar recurrence in the book Concrete Mathematics at the exercise 1.8

→ Reply

hellman_

9 years ago, # |

← Rev. 3 →

It quickly (in 1-2 elements) converges to 1, 1, 2, 3, 2, 1, 1, 2, 3, 2, 1, 1, ...

assume n >= 3

if a > b:
     print [1, 1, 2, 3, 2][(n - 3) % 5]
else:
     print [1, 1, 2, 3, 2][(n - 4) % 5]

PS: No proof, just a blind guess...

FIX: 1, 1, 2, 3, 2 corresponds to Q_n / n. Of course need to multiply the result by N.

→ Reply

zxqfl

9 years ago, # ^ |

Here are the first 10 terms when a = b = 1:

Q(1) = 1
Q(2) = 1
Q(3) = 6
Q(4) = 28
Q(5) = 24
Q(6) = 5
Q(7) = 1
Q(8) = 3
Q(9) = 36
Q(10) = 123

→ Reply

Matrix.code

9 years ago, # ^ |

any pattern???
I try to express the.equation in order of matrix. But how to do that???

→ Reply

hellman_

9 years ago, # ^ |

+11

The division is not rational, it's integer (truncated). So Q_n is divisible by n. But indeed in your case Q_n / n converges to 1, 1, 2, 3, 2 after 5th element, not 3rd.

Also I found another counterexamples: for these (a, b) pairs:

(3, 4), (3, 5), (4, 4), (4, 5), (4, 6), (5, 5), (5, 6), (6, 6).

All Q_n / n = 2(n ≥ 3). For other 1 ≤ a, b ≤ 100 pattern 1, 1, 2, 3, 2 follows.

→ Reply

hellman_

9 years ago, # ^ |

+11

Define $\text{[math]}$ . It is easy to check that for n ≥ 5 (because we can not assume that 2 divides b so n - 2 > 2) if we meet consequent T_i = 1, T_i + 1 = 1 than the following sequence is repeated infinitely: 1, 1, 2, 3, 2. For example for 1, 1 we have: $\text{[math]}$ . It is easy to prove these rules:

(1, 1) -> 2
(1, 2) -> 3
(2, 3) -> 2
(3, 2) -> 1
(2, 1) -> 1
and also (2, 2) -> 2

It's left to prove that for any a, b we will quickly see any of these patterns. The main idea is that $\text{[math]}$ factor does not affect value of T_n if n is large and T_n - 1 and T_n - 2 are small; and for any intermediate values x, y we quickly get to small T_n.

Let's assume we have i ≥ 5, T_i = x, T_i + 1 = y. Then T_i + 2 ≤ 3y, T_i + 3 ≤ 5 (put values in the formula and see).

If T_i + 2 = 1 then T_i + 3 ≤ 2 and so we have matched one of our rules: (1, 1) or (1, 2).

If T_i + 2 > 1 then T_i + 4 ≤ 3 (5/2+1).

if T_i + 4 = 3 then T_i + 5 ≤ 4, T_i + 6 ≤ 2, T_i + 7 ≤ 3 and we have matched one of the rules. (We could find (1, 3) but it is impossible (check two cases if T_i + 5 ≥ 3 or not));
if T_i + 4 = 2 then T_i + 5 ≤ 3 and we have matched one of the rules;
if T_i + 4 = 1 then T_i + 5 ≤ 2 and we have matched one of the rules.