BrainDen.com - Brain Teasers

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

Rationale

Spoiler

Let r5 = sqrt(5)

Let a=3+r5

Problem is find f(n) = last 3 digits before decimal point of a^n

Let a' = 3-r5 (the conjugate of a)

Note that a*a' = 4 and a + a' = 6

As DeeGee showed, a^2 = (3+r5)^2 = 9+6r5+5=14+6r5=14+6(a-3)=6a-4

So a^2 = 6a-4

Therefore a^n = 6a^(n-1) - 4a^(n-2)

Similarly for a': a'^2 = (3-r5)^2 = 9-6r5+5=14-6r5 = 14+6(a'-3) = 6a'-4

So a'^2=6a'-4

Therefore a'^n=6a'^(n-1)-4'^(n-2)

As a first try, consider g(n) = a^n + a'^n

Since a' < 1, then a'^n for all n is also < 1.

So a^n = g(n) - a'^n and the last 3 digits of a^n will be the last 3 digits of g(n)-1

g(n) = a^n + a'^n = (6a^(n-1) - 4a^(n-2)) + (6a'^(n-1)-4'^(n-2)) = 6*(a^(n-1) +a'^(n-1)) - 4(a^(n-2) +a'^(n-2))

g(n) = 6*g(n-1) - 4*g(n-2)

As a second try, consider h(n) = g(n) - 1 = 6*(h(n-1)+1) - 4*(h(n-2)+1) - 1 = 6*h(n-1)-4*h(n-2)+6-4-1 = 6*h(n-1)-4*h(n-2)+1

h(n) = 6*h(n-1)-4*h(n-2)+1

This is a recursive solution of degree 2, so we need two initial conditions.

g(1) = a + a' = 6, so h(1) = 5

g(2) = a^2 + a'^2 = 28, so h(2) = 27

So these three things define a recursive algorithm to get h(n):

1. h(1) = 5

2. h(2) = 27

3. h(n) = 6*h(n-1) - 4*h(n-2) + 1

We will still run out of memory, so we need to throw away things that don't matter.

Consider h(n) = x(n) + y(n) where y(n) = h(n) % 1000 (i.e. modulo 1000) and x(n) = h(n) - y(n)

x(n) cannot impact y(m) where m > n. This is because the future impact of x(n) is 6*x(n), followed by a -4*x(n).

So the two components of the future sum due to x(n) is first 6*x(n), followed by 2*x(n) because 2 = 6-4.

Neither of those components have any residual modulo 1000.

Therefore we can define f(n) = h(n) % 1000.

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

##### Share on other sites
• 3
On 3/13/2015 at 10:02 AM, gavinksong said:

it involves a conjugate

I was looking a this question yesterday, and while I understood this hint, I did not know how to apply it. Well, today while browsing another site, I stumbled upon a similar question concerning (1+√3)2015. The solution to that provided all the information needed to solve this one.

Spoiler

N = (3 + √5)n + (3 - √5)n is an integer. (All odd powers of √5 cancel)

(3 + √5)n = N - (3 - √5)n

0 < (3 - √5) < 1, so 0 < (3 - √5)n < 1 for all n > 0

N > (3 + √5)n > N - 1

Therefore, the last three digits before the decimal point for (3 - √5)n are the last three digits of (N - 1).

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.

Edited by Logophobic
had a + where there should have been a -

##### Share on other sites
• 1

Okay here's my attempt

So calculating (3 + sqrt5)^n

When I saw sqrt5 I immediately thought of its connection to the golden ratio & fibonacci numbers

The golden ratio "phi" = (1 + sqrt5)/2, one of two numbers holding the property phi^2 - phi - 1 = 0

the other being (1 - sqrt5)/2

Anyway phi^n has curious properties that let the exponential be reduced to multiples of itself added together with coefficients being Fibonacci numbers.

3 + sqrt5 = 2 * phi + 2 or 2*(1 + phi) = 2*phi^2 because phi^2 = phi + 1

so (3 + sqrt5)^n = 2^n * phi^(2n)

At this point I think you could use a lot of different properties of the golden ratio to get this number.

Notably

phi^k = F(k) * phi + F(k-1) where F(k) is the kth Fibonacci number

so=> 2^n * (F(2n) * phi + F(2n-1))

This should way be easier to calculate assuming you don't make any coding mistakes aka have a fast fibonacci calculator (non recursive - the recursive algorithm is complexity O(2^n) but the iterative method is much faster like O(n) I think) and so the whole latter term can be calculated pretty quickly, and if not because n is soooo huge well I'm pretty sure there are algorithms for calculating just the final digits of large fibonacci numbers. Don't quote me on that but let's roll with it! So now we have this number N(n) = (F(2n) * phi + F(2n-1)) = ((1+sqrt5)/2)^(2n)

and (3 + sqrt5)^n === 2^n * N(n)

This doesn't seem too expensive now because 2^n in binary is just a one bit followed by n-1 zero bits.

##### Share on other sites
• 0

The problem can be reduced to a simple matrix exponentiation. √5 does not ever need to be calculated.

##### Share on other sites
• 0

991

Um... Is this your answer for some value of n?

Do you have a general method?

##### Share on other sites
• 0

991

Um... Is this your answer for some value of n?

Do you have a general method?

It holds for 8 and 16 -- quick and dirty.

I took OP to suggest the answer is the same for all n sufficiently large, probably not true.

##### Share on other sites
• 0

i have no idea how you could solve this without computing at least a few decimal points of sqrt(5).

for example one possiblility might be multipying by 3 -sqrt(5), but then i would have to divide by this number at the end of the problem.

the fastest way i know of, would be to compute about 1000 decimal points of 3+sqrt(5),

and then use the fact that a^n * a^n = a^(2*n). ie something like

```v = 3 +sqrt(5)
while n != 0:
if n&1 == 0:
n -= 1
v *= (3+sqrt(5))
else:
n >>= 1
v *= v
print v
```
Edited by phil1882

##### Share on other sites
• 0

i have no idea how you could solve this without computing at least a few decimal points of sqrt(5).

for example one possiblility might be multipying by 3 -sqrt(5), but then i would have to divide by this number at the end of the problem.

the fastest way i know of, would be to compute about 1000 decimal points of 3+sqrt(5),

and then use the fact that a^n * a^n = a^(2*n). ie something like

```v = 3 +sqrt(5)
while n != 0:
if n&1 == 0:
n -= 1
v *= (3+sqrt(5))
else:
n >>= 1
v *= v
print v
```

That's a technique called 'fast exponentiation', and it can be used later on in the problem to evaluate a matrix exponentiation. However, I'm not sure it would speed up your operation quite fast enough. If you've computed 1000 digits, you're already using several megabytes to store a single value, all of which needs to be processed at least 31 times for a result that may or may not be correct. No, the answer is to bypass calculating the value of √5 completely. It's a math problem, not a coding problem.

I've never seen even-odd testing done like that before btw. Is it faster than using the remainder operator?

Edit -- of course, what I said above is just conjecture. I actually don't know how long it would take at all, but it probably still won't work for n = 2 billion.

Edited by gavinksong

##### Share on other sites
• 0

bumpitybump

Don't let the title scare you. It is not really that complicated.

Edited by gavinksong

##### Share on other sites
• 0

It is not really that complicated.

I expect not, or it would not be a good puzzle, just a lengthy calculation.

That said, I think we're all waiting for the arrival of an AHA! moment ... ##### Share on other sites
• 0

There are actually several solutions, so feel free to tackle the problem your way.

##### Share on other sites
• 0

Okay here's my attempt

So calculating (3 + sqrt5)^n

When I saw sqrt5 I immediately thought of its connection to the golden ratio & fibonacci numbers

The golden ratio "phi" = (1 + sqrt5)/2, one of two numbers holding the property phi^2 - phi - 1 = 0

the other being (1 - sqrt5)/2

Anyway phi^n has curious properties that let the exponential be reduced to multiples of itself added together with coefficients being Fibonacci numbers.

3 + sqrt5 = 2 * phi + 2 or 2*(1 + phi) = 2*phi^2 because phi^2 = phi + 1

so (3 + sqrt5)^n = 2^n * phi^(2n)

At this point I think you could use a lot of different properties of the golden ratio to get this number.

Notably

phi^k = F(k) * phi + F(k-1) where F(k) is the kth Fibonacci number

so=> 2^n * (F(2n) * phi + F(2n-1))

This should way be easier to calculate assuming you don't make any coding mistakes aka have a fast fibonacci calculator (non recursive - the recursive algorithm is complexity O(2^n) but the iterative method is much faster like O(n) I think) and so the whole latter term can be calculated pretty quickly, and if not because n is soooo huge well I'm pretty sure there are algorithms for calculating just the final digits of large fibonacci numbers. Don't quote me on that but let's roll with it! So now we have this number N(n) = (F(2n) * phi + F(2n-1)) = ((1+sqrt5)/2)^(2n)

and (3 + sqrt5)^n === 2^n * N(n)

This doesn't seem too expensive now because 2^n in binary is just a one bit followed by n-1 zero bits.

You, good sir, have just blown my mind. I have not seen this type of solution. In my mind, you are a true winner.

But there is still a problem lurking in your blind side. You would have to calculate either √5 or phi to an absurd amount of precision in order to multiply them by such a large integer. You would probably either run out of space or time.

The trick is to exclude irrational numbers entirely from the final calculation - or at least, that's what the trick is for one solution.

Edited by gavinksong

##### Share on other sites
• 0

@ unreality. LTNS. Nice to see you again. ##### Share on other sites
• 0

2 possible methods

Let a = 3 + r5

r5 means 50.5

Then a² = 14 + 6r5

Then a² = 6a - 4

Then, for any n

an = 6an-1 - 4an-2

Does this keep the 3 decimal places intact?

(3 + r5)n = x + y(r5)

This can be easily computed for any n

X is a digit so no problems there for decimal places

now, Let y(r5) = S

Then, Ln S = Ln y + (0.5) Ln 5

Once y is known, unsing log and then antilog the first 3 decimal places for S can be known accurately and hence for an

Edited by DeGe

##### Share on other sites
• 0

2 possible methods

Let a = 3 + r5

r5 means 50.5

Then a² = 14 + 6r5

Then a² = 6a - 4

Then, for any n

an = 6an-1 - 4an-2

Does this keep the 3 decimal places intact?

(3 + r5)n = x + y(r5)

This can be easily computed for any n

X is a digit so no problems there for decimal places

now, Let y(r5) = S

Then, Ln S = Ln y + (0.5) Ln 5

Once y is known, unsing log and then antilog the first 3 decimal places for S can be known accurately and hence for an

Hey, thanks for giving this puzzle some attention. That's pretty clever, turning it into a recursive definition, but unfortunately, I'm not sure it would keep the three decimal places intact. √5 can only be approximated to a finite precision in the first place, so if you perform enough operations on it, it'll eventually affect the ones digit. Or at least, there's no guarantee that it won't.

Agreed that x and y can eventually be found by summing the even and the odd binomial coefficients, respectively. But to calculate S from that would require knowing to what precision we need to calculate the square-root, log, and anti-log functions. It would probably be easier to simply multiply y and √5 after determining the required precision, but this method is rather ugly.

Let me rephrase the problem so that it is less ambiguous. There will still be multiple solutions.

How can you determine the last three digits of (3 + √5)n before the decimal using only integer operations?

Edited by gavinksong

##### Share on other sites
• 0

i had an idea of looking at the last three digits of powers of 5 and 3, but for 3 its not very good, its quite a long list. i'd say this problem is close to intractable.

or at least i dont see any good non mass calcuation solution to it for large powers.

##### Share on other sites
• 0

Let a = 3 + r5

r5 means 50.5

Then a² = 14 + 6r5

Then a² = 6a - 4

Then, for any n

an = 6an-1 - 4an-2

Does this keep the 3 decimal places intact?

Actually, DeGe, your first method is approaching one of the solutions, but it isn't quite there because it still uses irrational numbers in the final calculation.

Edited by gavinksong

##### Share on other sites
• 0

Not an answer, but I'm hoping to contribute to an Aha! moment...

To reduce overhead for large exponents, we could just mod 1000 to pass less costly numbers.

##### Share on other sites
• 0

If you simply calculate the value of (3+sqrt(5))

n for small values of n, you get

```1  5.2360679775
2  27.416407865
3  143.55417528
4  751.65942022
5  3935.7398201998
6  20607.801240319
7  107903.848161115
8  564991.884005414
9  2958335.91138802
10 15490047.9323065
11 81106943.9482868
12 424681471.960495
13 2223661055.96982
14 11643240447.9769
15 60964798463.9824
16 319215828991.987
17 1671435780095.99```
It's not clear to me why the decimal portion should approach one as it's raised to higher powers, if that's indeed what happens. Similarly strange things happen with other expressions of the form (X+sqrt(Y))n, such as (1+sqrt(2))n asymptotically bouncing between decimal values just below 0.999... and just above 0 that seem to converge toward zero/unity.

##### Share on other sites
• 0

If you simply calculate the value of (3+sqrt(5))

n for small values of n, you get
```1  5.2360679775
2  27.416407865
3  143.55417528
4  751.65942022
5  3935.7398201998
6  20607.801240319
7  107903.848161115
8  564991.884005414
9  2958335.91138802
10 15490047.9323065
11 81106943.9482868
12 424681471.960495
13 2223661055.96982
14 11643240447.9769
15 60964798463.9824
16 319215828991.987
17 1671435780095.99```
It's not clear to me why the decimal portion should approach one as it's raised to higher powers, if that's indeed what happens. Similarly strange things happen with other expressions of the form (X+sqrt(Y))n, such as (1+sqrt(2))n asymptotically bouncing between decimal values just below 0.999... and just above 0 that seem to converge toward zero/unity.

I will confirm that what you observed is true. You need to be clever.

##### Share on other sites
• 0
Spoiler

def sol(n):
if n == 1:
return 5;
if n == 2:
return 27;
a=5;b=27;i=2;
while i < n:
c = 6*b-4*a+1 % 1000;
a,b = b,c;
i += 1;
return b % 1000;

I think I got the answer thanks to some of the other hints and ideas posted.

##### Share on other sites
• 0

Answer for n = 2e9

Spoiler

407

Took too long to run in python, so rewrote in C.

#include <stdio.h>
#include <math.h>

int main(void){

unsigned int a,b,c,i,n;
n = 2*pow(10,9);

if (n == 1){
printf("%d",5);
return 0;
}
if (n == 2){
printf("%d",27);
return 0;
}
i = 2;
a=5;
b=27;
while (i < n){
c = (6*b-4*a+1) % 1000;
a = b;
b = c;
i++;
}
printf ("%d",b % 1000);
return 0;
}

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

×