The Fibonacci sequence is defined by the recurrence relation:
Hence the first 12 terms will be:
The 12th term, , is the first term to contain three digits.
What is the first term in the Fibonacci sequence to contain 1000 digits?
#!/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 clojure fibonacci.clj real 0m0.751s user 0m1.388s sys 0m0.060s
fibs :: [Integer] fibs = 0 : 1 : zipWith (+) fibs (tail fibs) main :: IO () main = print $ head [i | i <- [1..], (==1000) . length . show $ fibs !! i]
$ ghc -O2 -o fibonacci fibonacci.hs $ time ./fibonacci real 0m0.125s user 0m0.120s sys 0m0.000s
#!/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