A Complicated Numbers Problem

[gavinksong]

This is another problem from Google Code Jam that blew my mind.
It is still blowing my mind. It just so happens to be from the same round as the problem I posted earlier.
 

Problem
In this problem, you have to find the last three digits before the decimal point for the number (3 + √5)ⁿ.

Like before, there is a small input and a large input for this problem. For the large input, n can reach up to 2 billion. Thus, in order to calculate the answer in a reasonable amount of time (and precision*), some key mathematical insights are required.

 

What are they?

 

*for non-coders: since computers cannot store real numbers with infinite precision, most operations on "floating point numbers" cause a gradual loss in precision. In our case, it would almost definitely result in an incorrect answer.

[jasen]

First count (sqrt 5), in very high precision.

Then use pascal triangle formula.

then group every odd exponent of sqrt (5). then multiple it by (sqrt 5) just once, you will get right answer.

you will get better precision.

example

(a+b)⁵ = a⁵ + 5a⁴b + 10a³b² + 10a²b³ + 5ab⁴ + b⁵

         = a⁵ + b(5a⁴ + 10a²b² +b⁴) + 10a³b² + 5ab⁴

(3 + √5)⁵ = 3⁵ + √5(5.3⁴ + 10.3^2.5 + 25) + 10.3^3.5+ 5.3.25 = 1968 + √5*880 

[jasen]

I think I have found the answer

Spoiler

 

I just found intersting connection 

(a+b)⁵ + (a-b)⁵ =  (a⁵ + 5a⁴b + 10a³b² + 10a²b³ + 5ab⁴ + b⁵ ) + (a⁵ - 5a⁴b + 10a³b² - 10a²b³ + 5ab⁴ - b⁵ ) = 2a⁵ + 20a³b² + 10ab⁴

there you don't have to count odd exponent of b. 

after I tried it in haskell,  (3 + √5)ⁿ  + (3 - √5)ⁿ  is very close with (3 + √5)ⁿ

so just count (3 + √5)ⁿ  + (3 - √5)^n, with above ways and substract the value with 1. 

example : 

(3 + √5)⁴ = 751.6594202199647

(3 + √5)⁴  + (3 - √5)⁴ = 752

 

(3 + √5)⁵ = 3935.739820199815

(3 + √5)⁵  + (3 - √5)⁵ =  3936

 

 

[gavinksong]

On February 3, 2016 at 6:18 AM, mmiguel said:

 

  Hide contents

The final definition is:

1. f(1) = 5

2. f(2) = 27

3. f(n) = 6*f(n-1) - 4*f(n-2) + 1 % 1000

 

Nice job! As you said, our fellow brain-denizens had all the bits and pieces (especially DeGe and Logophobic, also Molly Mae). Well done on putting them all together!

There IS one last piece of the puzzle required to make n = 2 billion run in a reasonable amount of time.

Spoiler

Let's review:

 

| f(n)   | = | 6   4 | * | f(n-1)
| f(n-1) |   | 1   0 |   | f(n-2)

 

[gavinksong]

On February 3, 2016 at 6:18 AM, mmiguel said:

 

  Hide contents

The final definition is:

1. f(1) = 5

2. f(2) = 27

3. f(n) = 6*f(n-1) - 4*f(n-2) + 1 % 1000

 

Nice job! As you said, our fellow brain-denizens had all the bits and pieces (especially DeGe and Logophobic, also Molly Mae). Well done on putting them all together!

There IS one last piece of the puzzle required to make n = 2 billion run in a reasonable amount of time.

Spoiler

You could represent the third part of your definition as a matrix operation. For example,

| f(n)   |   | 6  -4   1|   | f(n-1)|
| f(n-1) | = | 1   0   0| * | f(n-2)|
| 1      |   | 0   0   1|   | 1     |

Unraveling the recursion is equivalent to multiplying the matrix to itself over and over again.

| f(n)   |   | 6  -4   1|^(n-2)   | f(2)|
| f(n-1) | = | 1   0   0|    *    | f(1)|
| 1      |   | 0   0   1|         | 1   |

Now we can use fast exponentiation, which phil1882 brought up earlier. Basically, the idea is to repeatedly halve the exponent by squaring the base.

A^n = (A^2)^(n/2)

On December 30, 2015 at 9:47 AM, Logophobic said:

 

  Hide contents

Interesting to note: there are only 44 possible results, recurring in a cycle of length 500. We can index these results and use (n mod 500) to find the result for any n.

I didn't know this. If this is true, this is indeed an alternative solution.