Google Code Jam 2008: Round 1A Question 3

Question

At Google Code Jam 2008 round 1A, there is problem:

Calculate last three digits before the decimal point for the number (3+sqrt(5))^n

n can be big number up to 1000000.
For example: if n = 2 then (3+sqrt(5))^2 = 27.4164079... answer is 027.
For n = 3: (3+sqrt(5))^3 = 3**935**.73982... answer is 935.

One of the solution is to create matrix M 2x2 : [[0, 1], [-4, 6]] than calculate matrix P = M^n, Where calculation preformed by modulo 1000. and the result is (6*P[0,0] + 28*P[0,1] - 1) mod 1000.

Who can explain me this solution?

Answer 1

I don't know how to explain that, but the auther of the problem have compose this analysis.

Answer 2

I'll present a method to solve this problem without even understanding the solution.

Assuming that you are familiar with the fibonacci numbers:

ghci> let fib = 0 : 1 : zipWith (+) fib (tail fib)
ghci> take 16 fib
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]

And are also familiar with its closed form expression:

ghci> let calcFib i = round (((1 + sqrt 5) / 2) ^ i / sqrt 5)
ghci> map calcFib [0..15]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]

And you notice the similarity of ((1 + sqrt 5) / 2)ⁿ and (3 + sqrt 5)ⁿ.

From here one can guess that there is probably a series similar to fibonacci to calculate this.

But what series? So you calculate the first few items:

ghci> let calcThing i = floor ((3 + sqrt 5) ^ i)
ghci> map calcThing [0..5]
[1,5,27,143,751,3935]

Guessing that the formula is of the form:

thing_n = a*thing_n-1 + b*thing_n-2

We have:

27 = a*5 + b*1

143 = a*27 + b*5

We solve the linear equations set and get:

thing_n = 4*thing_n-1 + 7*thing_n-2 (a = 4, b = 7)

We check:

ghci> let thing = 1 : 5 : zipWith (+) (map (* 4) (tail thing)) (map (* 7) thing)
ghci> take 10 thing
[1,5,27,143,761,4045,21507,114343,607921,3232085]
ghci> map calcThing [0..9]
[1,5,27,143,751,3935,20607,107903,564991,2958335]

Then we find out that sadly this does not compute our function. But then we get cheered by the fact that it gets the right-most digit right. Not understanding why, but encouraged by this fact, we try to something similar. To find the parameters for a modified formula:

thing_n = a*thing_n-1 + b*thing_n-2 + c

We then arrive at:

thing_n = 6*thing_n-1 - 4*thing_n-2 + 1

We check it:

ghci> let thing =
        1 : 5 : map (+1) (zipWith (+)
          (map (*6) (tail thing))
          (map (* negate 4) thing))
ghci> take 16 thing == map calcThing [0..15]
True