Tuesday, August 13, 2013

Problem 25 - No code Necessary

Problem 25 asks for which fibonacci number is the first to contain 1000 digits: as a method for solving this by hand came to mind pretty quickly, I didn't find it necessary to write any code, as I could quickly write down a solution which I could feed into a calculator:
The nth fibonacci number can be expressed as fib(n) = (phi^n + (-phi)^-n / sqrt(5)), where phi=1.618... is the golden ratio.
As n is large, the second term in the sum is nearly 0, so we need only find the smallest integer n such that

phi^n / sqrt(5) > 10^999

Solving for n gives

n = ceil ( 999 * log_phi (10) + log_phi(sqrt(5)) )
So, now I have finished 25 problems and therefore reached "Level 1" on Project Euler. Maybe the next problem will require actually writing some code.

No comments:

Post a Comment