## Question

The Fibonacci sequence is defined by the recurrence relation:

$\displaystyle 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:

\displaystyle \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?

## Clojure

#!/usr/bin/env clojure
(def fibs
(lazy-cat [(BigInteger/ZERO) (BigInteger/ONE)] (map + fibs (rest fibs))))

(println (count (take-while #(< % (.pow (BigInteger/TEN) 999)) fibs)))
$time ./fibonacci real 0m0.125s user 0m0.120s sys 0m0.000s ## Ruby #!/usr/bin/env ruby i = 1 t1, t2 = 0, 1 while t2.to_s.length < 1000 t1, t2 = t2, t1 + t2 i += 1 end puts i $ time ruby fibonacci.rb
real   0m0.069s
user   0m0.060s
sys    0m0.008s

Questions? Comments? Send me an email: z@chdenton.com