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.

## Question

## 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.

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.## Link to comment

## Share on other sites

## 29 answers to this question

## Recommended Posts

## Join the conversation

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