Grind Report 25

Problem 25

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n-1 + F_n-2, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

*WARNING: This contains the solution!*

1000 digits, eh? That's a lot of digits. And once again there are two ways to solve this. Brute force or some method paved with gold. Amazingly I went with brute force this time since it was the one that required programming, but I'll go over the gold way as well.

My brute force method is kind of cheating but it is smart cheating? This raises the moral issue of whether cheating is acceptable as long as it is done in an intelligent manner. Anyways, the way I cheated is that while calculating Fibonacci numbers to find the first one with 1000 digits, instead of keeping all of the digits, which would be impossible with built in types, I just would cut off the less significant digits when the number got to a certain size and keep count of how many digits I cut off. This method worked like a charm and the algorithm is very fast! :)

The golden method is real gold! If you ever took calculus with Mr. Penner at Red Bluff High School, then you would know what the golden ratio is - (1 + sqrt(5)) / 2. You would also know that F_n/F_n-1 converges to this golden ratio, which is known as phi. Taking this golden ratio and using it with the fact that if you take the ceil(log₁₀(n)) then you will actually the number of digits that number contains, we can solve this problem by hand (preferably with a calculator in it). This looks something like...

ceil(((999 + log₁₀(sqrt(5)))/log₁₀((1 + sqrt(5))/2))

Yay! Math!

Oh, yeah. Here is my brute force goodness.

#include <iostream>
#include <math.h>

int main()
{
 long long f = 1;
 long long fn = 1;
 int count = 0;
 int i = 2;
 while (count + (int)ceil(log10((long double)fn)) < 1000)
 {
  long long temp = fn;
  fn += f;
  f = temp;
  if (fn > 1000000000000)
  {
   fn /= 10;
   f /= 10;
   ++count;
  }
  ++i;
 }
 std::cout << i;
}

*saved game*