Project Euler Problem 25 Solution

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?

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 clojure fibonacci.clj
real   0m0.936s
user   0m1.828s
sys    0m0.102s

Haskell

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.137s
user   0m0.136s
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.095s
user   0m0.094s
sys    0m0.000s

Rust

fn main() {
    let mut a = vec![0];
    let mut b = vec![1];
    let mut n = 1;
    while b.len() < 1000 {
        let tmp = b.clone();
        let mut carry = 0;
        for i in 0..b.len() {
            if i >= a.len() {
                a.push(0);
            }
            let mut digit = a[i];
            digit = b[i] + digit + carry;
            carry = digit / 10;
            a[i] = digit % 10;
        }
        if carry > 0 {
            a.push(carry);
        }
        b = a;
        a = tmp;
        n += 1;
    }
    println!("{}", n);
}

$ rustc -C target-cpu=native -C opt-level=3 -o fibonacci fibonacci.rs
$ time ./fibonacci
real   0m0.008s
user   0m0.007s
sys    0m0.000s