BrainDen.com - Brain Teasers
• 0

# A Complicated Numbers Problem

## Question

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)n.

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.

## Recommended Posts

• 0

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)5 = a5 + 5a4b + 10a3b2 + 10a2b3 + 5ab4 + b5

= a5 + b(5a4 + 10a2b2 +b4) + 10a3b+ 5ab4

(3 + √5)5 = 35 + √5(5.34 + 10.32.5 + 25) + 10.33.5+ 5.3.25 = 1968 + √5*880

##### Share on other sites

• 0

I think I have found the answer

Spoiler

I just found intersting connection

(a+b)5 + (a-b)=  (a5 + 5a4b + 10a3b2 + 10a2b3 + 5ab4 + b5 ) + (a5 - 5a4b + 10a3b2 - 10a2b3 + 5ab4 - b5 ) = 2a5 + 20a3b2 + 10ab4

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

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

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

example :

(3 + √5)4 = 751.6594202199647

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

(3 + √5)5 = 3935.739820199815

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

##### Share on other sites

• 0
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)

##### Share on other sites

• 0
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.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.