Problem

The Fibonacci sequence is defined by the recurrence relation:

$$
Fn = F{n-1} + F_{n-2} \text{ where } F_1 = 1 \text{ and } F_2 = 1
$$

Hence the first 12 terms will be:

$$
\begin{split}
F_1 &= 1 \
F_2 &= 1 \
F_3 &= 2 \
F_4 &= 3 \
F_5 &= 5 \
F_6 &= 8 \
F_7 &= 13 \
F_8 &= 21 \
F9 &= 34 \
F{10} &= 55 \
F{11} &= 89 \
F{12} &= 144
\end{split}
$$

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?

Answer

4782

Python

import itertools


# Because the target number is relatively small, we simply compute each Fibonacci number starting
# from the beginning until we encounter one with exactly 1000 digits. The Fibonacci sequence grows
# exponentially with a base of about 1.618, so the numbers in base 10 will lengthen by one digit
# after every log10(1.618) ~= 4.78 steps on average. This means the answer is at index around 4780.
def compute():
	DIGITS = 1000
	prev = 1
	cur = 0
	for i in itertools.count():
		# At this point, prev = fibonacci(i - 1) and cur = fibonacci(i)
		if len(str(cur)) > DIGITS:
			raise RuntimeError("Not found")
		elif len(str(cur)) == DIGITS:
			return str(i)
		
		# Advance the Fibonacci sequence by one step
		prev, cur = cur, prev + cur


if __name__ == "__main__":
	print(compute())

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

Haskell

fibs ::  [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

main ::  IO ()
main = print $ head [i | i <- [1..], (==1000) . length . show $ fibs !! i]

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)))

Mathematica

(* 
 * Because the target number is relatively small, we simply compute each Fibonacci number starting
 * from the beginning until we encounter one with exactly 1000 digits. The Fibonacci sequence grows
 * exponentially with a base of about 1.618, so the numbers in base 10 will lengthen by one digit
 * after every log10(1.618) ~= 4.78 steps on average. This means the answer is at index around 4780.
 *)
digits = 1000;
i = 0;
While[Fibonacci[i] < 10^(digits-1), i++]
i

Java

import java.math.BigInteger;


public final class p025 implements EulerSolution {
	
	public static void main(String[] args) {
		System.out.println(new p025().run());
	}
	
	
	/* 
	 * Because the target number is relatively small, we simply compute each Fibonacci number starting
	 * from the beginning until we encounter one with exactly 1000 digits. The Fibonacci sequence grows
	 * exponentially with a base of about 1.618, so the numbers in base 10 will lengthen by one digit
	 * after every log10(1.618) ~= 4.78 steps on average. This means the answer is at index around 4780.
	 */
	
	private static final int DIGITS = 1000;
	
	public String run() {
		BigInteger lowerThres = BigInteger.TEN.pow(DIGITS - 1);
		BigInteger upperThres = BigInteger.TEN.pow(DIGITS);
		BigInteger prev = BigInteger.ONE;
		BigInteger cur = BigInteger.ZERO;
		for (int i = 0; ; i++) {
			// At this point, prev = fibonacci(i - 1) and cur = fibonacci(i)
			if (cur.compareTo(upperThres) >= 0)
				throw new RuntimeException("Not found");
			else if (cur.compareTo(lowerThres) >= 0)
				return Integer.toString(i);
			
			// Advance the Fibonacci sequence by one step
			BigInteger temp = cur.add(prev);
			prev = cur;
			cur = temp;
		}
	}
	
}