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.

[mmiguel]

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

 

 

 

 

[Logophobic]

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)²⁰¹⁵. The solution to that provided all the information needed to solve this one.

Spoiler

 

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

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

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

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

Therefore, the last three digits before the decimal point for (3 - √5)ⁿ 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 December 30, 2015 by Logophobic
had a + where there should have been a -

[unreality]

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.

[gavinksong]

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

[bonanova]

991

[gavinksong]

991

 

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

Do you have a general method?

[bonanova]

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.

[gavinksong]

it involves a conjugate

[phil1882]

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 March 13, 2015 by phil1882

[gavinksong]

 

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 March 13, 2015 by gavinksong

[gavinksong]

bumpitybump

 

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

Edited March 29, 2015 by gavinksong

[bonanova]

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

[gavinksong]

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

[gavinksong]

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 April 2, 2015 by gavinksong

[bonanova]

@ unreality. LTNS. Nice to see you again.

[DeGe]

2 possible methods

Let a = 3 + r5

r5 means 5^0.5

 

Then a² = 14 + 6r5

 

Then a² = 6a - 4

 

Then, for any n

 

aⁿ = 6a^n-1 - 4a^n-2

 

Does this keep the 3 decimal places intact?

 

 

(3 + r5)ⁿ = 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 aⁿ

 

Edited April 24, 2015 by DeGe

[gavinksong]

2 possible methods

Let a = 3 + r5

r5 means 5^0.5

 

Then a² = 14 + 6r5

 

Then a² = 6a - 4

 

Then, for any n

 

aⁿ = 6a^n-1 - 4a^n-2

 

Does this keep the 3 decimal places intact?

 

 

(3 + r5)ⁿ = 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 aⁿ

 

 

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)ⁿ before the decimal using only integer operations?

Edited April 26, 2015 by gavinksong

[phil1882]

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.

[gavinksong]

Let a = 3 + r5

r5 means 5^0.5

 

Then a² = 14 + 6r5

 

Then a² = 6a - 4

 

Then, for any n

 

aⁿ = 6a^n-1 - 4a^n-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 April 27, 2015 by gavinksong

[Molly Mae]

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.

[plasmid]

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

ⁿ 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))ⁿ, such as (1+sqrt(2))ⁿ asymptotically bouncing between decimal values just below 0.999... and just above 0 that seem to converge toward zero/unity.

[gavinksong]

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

ⁿ 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))ⁿ, such as (1+sqrt(2))ⁿ 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.

[CaptainEd]

Impressive

[mmiguel]

Spoiler

Python answer

 

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.

[mmiguel]

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;
}