Matrix.code's blog

A mathmetical Recurrence
By Matrix.code, 10 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 ??
  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
»
10 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

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 Qn / n. Of course need to multiply the result by N.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      The division is not rational, it's integer (truncated). So Qn is divisible by n. But indeed in your case Qn / 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 Qn / n = 2(n ≥ 3). For other 1 ≤ a, b ≤ 100 pattern 1, 1, 2, 3, 2 follows.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Define . 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 Ti = 1, Ti + 1 = 1 than the following sequence is repeated infinitely: 1, 1, 2, 3, 2. For example for 1, 1 we have: . 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 factor does not affect value of Tn if n is large and Tn - 1 and Tn - 2 are small; and for any intermediate values x, y we quickly get to small Tn.

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

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

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

        • if Ti + 4 = 3 then Ti + 5 ≤ 4, Ti + 6 ≤ 2, Ti + 7 ≤ 3 and we have matched one of the rules. (We could find (1, 3) but it is impossible (check two cases if Ti + 5 ≥ 3 or not));
        • if Ti + 4 = 2 then Ti + 5 ≤ 3 and we have matched one of the rules;
        • if Ti + 4 = 1 then Ti + 5 ≤ 2 and we have matched one of the rules.
        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          So for the algorithm:

          • compute Tn up to let's say 20 elements and return n * Tn if n ≤ 20 or n * Ti, where .
          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +23 Vote: I do not like it

            FAIL, I solved another problem.

            instead of

            .

            → Reply