Problem 25(1000-digit Fibonacci number)

Problem 25(1000-digit Fibonacci number)

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

The 12th term, F12, is the first term to contain three digits.

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

 

In Python:

#PE25 1000-digit Fibonacci number
import time

startTime = time.time()
fibo = [1, 1]

while(True):
    fibo.append(fibo[-2] + fibo[-1])
    if len(str(fibo[-1])) > pow(10, 3) - 1:
        break

print(len(fibo))
print(time.time() - startTime, "seconds")

Run time: 0.05464005470275879 seconds

 

In Java:

//Euler25 1000-digit Fibonacci number
package project_euler21_30;

import java.util.ArrayList;
import java.math.BigInteger;

public class Euler25 {
	public static void main(String[] args) {
		long startTime = System.currentTimeMillis();
		double numDigit = 0;
		ArrayList<BigInteger> fibo = new ArrayList<BigInteger>();
		fibo.add(new BigInteger("1"));
		fibo.add(new BigInteger("1"));
		while(true) {
			fibo.add(fibo.get(fibo.size() - 2).add(fibo.get(fibo.size() - 1)));
			numDigit = fibo.get(fibo.size() - 1).toString().length();
			if ( numDigit > Math.pow(10, 3) - 1) {
				break;
			}
		}
		System.out.println(fibo.size());
		long endTime = System.currentTimeMillis();
		System.out.println((double)(endTime - startTime)/(double)1000 + "seconds");
	}
}

Run time: 0.423seconds

 

Solution: 4782