Overview

 

Question

The Fibonacci sequence is defined by the recurrence relation:

\[F_n = F_{n−1} + F_{n−2} \text{ where } F_1 = 1 \text{ and } F_2 = 1\]

Hence the first 12 terms will be:

\[ \begin{aligned} F_1 &= 1 \\\\ F_2 &= 1 \\\\ F_3 &= 2 \\\\ F_4 &= 3 \\\\ F_5 &= 5 \\\\ F_6 &= 8 \\\\ F_7 &= 13 \\\\ F_8 &= 21 \\\\ F_9 &= 34 \\\\ F_{10} &= 55 \\\\ F_{11} &= 89 \\\\ F_{12} &= 144 \end{aligned} \]

The 12th term, \(F_{12}\), is the first term to contain three digits.

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

click for answer

4782

Solutions

 

Ruby

 fibonacci.rb https://raw.github.com/addamh/euler/master/025/fibonacci.rb download
#!/usr/bin/env ruby

a = b = 1
i = 2
while b.to_s.length < 1000
   a, b = b, a+b
   i += 1
end
puts i
$ time ruby fibonacci.rb
real	0m0.391s
user	0m0.384s
sys	0m0.006s