• 829
• 6
• 14

• 145.5k
• 22
• 190
• 478

• 507
• 1
• 5
• 11

I have recently completed [problem 25 from the project Euler site.][1]

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 first term in the Fibonacci sequence to contain 1000 digits?

I have solved this problem in Java, however, the execution time is fairly slow, and, I am looking for ways to improve it; below is my code, as well as the output given:

import java.util.ArrayList;
import java.math.BigInteger;
public class ProjectEuler25 {
 public static void main(String [] args) {
 long start = System.nanoTime();
 ArrayList<BigInteger> fibonacciNumbers = new ArrayList<BigInteger>();
 boolean validNo = true;
 int x = 2;
 BigInteger tempAns = null;
 fibonacciNumbers.add(BigInteger.valueOf(1));
 fibonacciNumbers.add(BigInteger.valueOf(1));
 do {
 tempAns = fibonacciNumbers.get(x-1).add(fibonacciNumbers.get(x-2));
 fibonacciNumbers.add(tempAns);
 x++;
 if(tempAns.toString().length() >= 1000) {
 validNo = false;
 }
 } while (validNo == true);
 Long stop = System.nanoTime();
 System.out.println("The first term in the Fibonacci sequence to contain 1,000 digits is term: " + fibonacciNumbers.size());
 System.out.println("Execution time: " + ((stop - start) / 1e+6) + " ms");
 }
}

Output:

The first term in the Fibonacci sequence to contain 1,000 digits is term: 4782

Execution time: 220.858659 ms

I know that it is possible to solve this problem in C# in 2ms. I have provided the code for this solution below:

int i = 0;
int cnt = 2;
BigInteger limit = BigInteger.Pow(10, 999);
BigInteger[] fib = new BigInteger[3];
 
fib[0] = 1;
fib[2] = 1;
 
while (fib[i] <= limit) {
 i = (i + 1) % 3;
 cnt++;
 fib[i] = fib[(i + 1) % 3] + fib[(i + 2) % 3];
}

C# code sourced from [here][2].

From looking at the C# code, the one thing which stands out to me, is maybe there is a better way to store the previous numbers than using an ArrayList? [1]: https://projecteuler.net/problem=25 [2]: http://www.mathblog.dk/project-euler-25-fibonacci-sequence-1000-digits/